[백준 - 16916] 부분 문자열

문제링크

첫번째 시도 (시간초과)

• contains 함수 사용

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val s = bufferedReader.readLine()
    val p = bufferedReader.readLine()
    if (s.contains(p)) {
        bufferedWriter.write("1")
    } else {
        bufferedWriter.write("0")
    }
    
    bufferedReader.close()
    bufferedWriter.close()
}

두번째 시도 (실패)

• 예외 케이스가 있을텐데 예외 케이스를 찾는게 쉽지가 않네요ㅠㅠ

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val s = bufferedReader.readLine()
    val p = bufferedReader.readLine()

    var j = 0
    var answer = "0"
    for (i in s.indices) {
        if (s[i] == p[j]) {
            j++
            if (j == p.length - 1) {
                answer = "1"
                break
            }
        } else {
            j = 0
        }
    }
    bufferedWriter.write("$answer")


    bufferedReader.close()
    bufferedWriter.close()
}

세번째 시도 (성공)

• KMP 알고리즘

fun main() {
    val bufferedReader = System.`in`.bufferedReader()
    val bufferedWriter = System.out.bufferedWriter()

    val s = bufferedReader.readLine()
    val p = bufferedReader.readLine()
    if (kmp(s, p)) bufferedWriter.write("1")
    else bufferedWriter.write("0")

    bufferedReader.close()
    bufferedWriter.close()
}

fun kmp(baseString: String, searchString: String): Boolean {
    val piArray = getPiArray(searchString)
    var j = 0
    for (i in baseString.indices) {
        while (j > 0 && baseString[i] != searchString[j]) {
            j = piArray[j - 1]
        }
        if (baseString[i] == searchString[j]) {
            if (j == searchString.length - 1) return true
            j++
        }
    }
    return false
}

fun getPiArray(searchString: String): Array<Int> {
    val length = searchString.length
    val array = Array(length) { 0 }
    var j = 0
    for (i in 1 until length) {
        while (j > 0 && searchString[j] != searchString[i]) {
            j = array[j - 1]
        }
        if (searchString[j] == searchString[i]) {
            array[i] = ++j
        }
    }
    return array
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.