Advertisement
vkazar

Untitled

May 21st, 2024
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.27 KB | None | 0 0
  1. import java.io.BufferedReader
  2. import java.io.InputStreamReader
  3.  
  4. fun main() {
  5.     val root = Node()
  6.     val buffer = BufferedReader(InputStreamReader(System.`in`))
  7.     val inputString = buffer.readLine()
  8.     repeat(buffer.readLine().toInt()) {
  9.         root.add(buffer.readLine().reversed())
  10.     }
  11.     val dp = BooleanArray(inputString.length + 1)
  12.     dp[0] = true
  13.  
  14.     for (i in 1..dp.lastIndex) {
  15.         var curNode = root
  16.         var stringIndex = i - 1
  17.         while (stringIndex >= 0) {
  18.             val curChar = inputString[stringIndex]
  19.             curNode = curNode.followings[curChar] ?: break
  20.             if (curNode.isTerminal && dp[stringIndex]) {
  21.                 dp[i] = true
  22.                 break
  23.             }
  24.             --stringIndex
  25.         }
  26.     }
  27.     if (dp.last()) println("YES")
  28.     else println("NO")
  29. }
  30.  
  31. class Node {
  32.     var isTerminal = false
  33.     val followings = mutableMapOf<Char, Node>()
  34. }
  35.  
  36. fun Node.add(string: String, curPos: Int = 0): Node {
  37.     return if (curPos == string.length) {
  38.         isTerminal = true
  39.         this
  40.     } else {
  41.         val nextChar = string[curPos]
  42.         this.followings.putIfAbsent(nextChar, Node())
  43.         val nextNode = this.followings[nextChar]
  44.         nextNode!!.add(string, curPos + 1)
  45.     }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement