Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader
- import java.io.InputStreamReader
- fun main() {
- val root = Node()
- val buffer = BufferedReader(InputStreamReader(System.`in`))
- val inputString = buffer.readLine()
- repeat(buffer.readLine().toInt()) {
- root.add(buffer.readLine().reversed())
- }
- val dp = BooleanArray(inputString.length + 1)
- dp[0] = true
- for (i in 1..dp.lastIndex) {
- var curNode = root
- var stringIndex = i - 1
- while (stringIndex >= 0) {
- val curChar = inputString[stringIndex]
- curNode = curNode.followings[curChar] ?: break
- if (curNode.isTerminal && dp[stringIndex]) {
- dp[i] = true
- break
- }
- --stringIndex
- }
- }
- if (dp.last()) println("YES")
- else println("NO")
- }
- class Node {
- var isTerminal = false
- val followings = mutableMapOf<Char, Node>()
- }
- fun Node.add(string: String, curPos: Int = 0): Node {
- return if (curPos == string.length) {
- isTerminal = true
- this
- } else {
- val nextChar = string[curPos]
- this.followings.putIfAbsent(nextChar, Node())
- val nextNode = this.followings[nextChar]
- nextNode!!.add(string, curPos + 1)
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement