문자열 검색 알고리즘 찾고자 하는 문자열의 suffix(접두사) 와 prefix(접미사)를 활용해 문자열을 검색한다.
![[출처] 배하람 블로그 https://baeharam.github.io/posts/algorithm/kmp/](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/5cdb3364-09dc-4aaf-88cd-dfe31dcd5c7b/kmp_brute_force.png)
[출처] 배하람 블로그 https://baeharam.github.io/posts/algorithm/kmp/
찾고자 하는 문자열 (S) 에서 다른 인덱스들에 대해서 접두사와 접미사가 일치하는 부분을 구한다. (실패 함수 생성)
→ 일치하지 않을 시 그만큼 탐색하지 않고 건너 뛸 수 있기 때문이다.
변수 begin을 H의 인덱스로, 일치하는 개수를 m이라고 하면
→ *begin - F(m-1)*만큼 begin을 옮겨주고 m을 0으로 만들어준다.

만약 ABABAB라는 문자열의 실패함수를 만든다고 하면 아래와 같다

→ 실패함수의 F(k)라고 한다면 k번째 인덱스에서 접두사와 접미사가 일치하는 최대길이를 뜻한다.
결과적으로 실패함수로 0 0 1 2 3 4 라는 결과를 저장한다.
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val stdString = br.readLine()
val pattern = br.readLine()
print(kmp(stdString, pattern))
}
private fun kmp(standard: String, pattern: String): Int {
val lpsTable: IntArray = getLpsTable(pattern)
val standardSize = standard.length
val patternSize = pattern.length
var answer = 0
var j = 0
for (i in 0 until standardSize) {
while (j > 0 && standard[i] != pattern[j]) {
j = lpsTable[j - 1]
}
if (standard[i] == pattern[j]) {
if (j == patternSize - 1) {
answer = 1
break
} else {
j++
}
}
}
return answer
}
private fun getLpsTable(string: String): IntArray {
val patternSize = string.length
val table = IntArray(patternSize) { 0 }
var j = 0
// 0일때는 항상 0이니까 생략해준다.
for (i in 1 until patternSize) {
while (j > 0 && string[i] != string[j]) {
j = table[j - 1]
}
if (string[i] == string[j]) {
table[i] = ++j
}
}
return table
}