16916번: 부분 문자열

문제 출처 : https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

언어 : Kotlin

 

문제 설명 :

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

 

입력 :

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

 

출력 :

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

입출력 예 :

입력	출력
baekjoon aek	1
baekjoon bak	0
baekjoon joo	1
baekjoon oone	0
baekjoon online	0
baekjoon baekjoon	1

 

풀이 : 

처음에 단순히 regionMatches 함수를 사용해 풀었다가 시간초과를 겪어 KMP 알고리즘으로 바꾸어 풀었다.

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

lateinit var table: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val s = readLine()
    val p = readLine()
    makeTable(p)
    bw.write("${search(s, p)}")
    bw.flush()
    bw.close()
}

fun search(str: String, pattern: String): Int {
    var idx = 0
    for (i in str.indices) {
        while (idx > 0 && str[i] != pattern[idx]) idx = table[idx - 1]
        if (str[i] == pattern[idx]) {
            if (idx == pattern.length - 1) return 1 else idx++
        }
    }

    return 0
}

fun makeTable(pattern: String) {
    var idx = 0
    table = IntArray(pattern.length)
    for (i in 1 until pattern.length) {
        while (idx > 0 && pattern[i] != pattern[idx]) idx = table[idx - 1]
        if (pattern[i] == pattern[idx]) { idx++; table[i] = idx }
    }
}