KMP, Rabin-Karp(Rolling-hash) 알고리즘. O(n) 의 time complexity 로 해결된다는 것을 암기해 놓자.

string arr { abc, adb, ade}

string arr2 { ade };

KMP

arr2 의 "ade" 가 arr에 있는지 확인하고 있다면 index를 return 받는다 라는 경우.

매칭을 시킬 때 이미 확인 된 조건들은 다시 확인 할 필요가 없는 것이다.

Rabin-Karp(Rolling-hash)

arr2의 "ade" hash 값을 알아낸다. 그리고 arr에서 window개념으로 한칸씩 옮기며 같은 hash값을 찾은 후, 값이 들어맞는지 확인하면 된다.

https://leetcode.com/problems/implement-strstr/

Input: haystack = "hello", needle = "ll"
Output: 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

음... 영상에서의 KMP 이론을 보고 코드를 짜봤으나 계속 에러가 나서 뭔가 이상함을 감지하고

다른 블로그를 참고했다.

https://vvshinevv.tistory.com/2 친절하게 한단계씩 잘 가르쳐줬다.

"aabaaabaaac" "aabaaac"

문제는 아래의 "aabaaac" 에서 발생했다. 내가 짠 코드대로라면 fail의 여부를 담는 배열에

{0, 1, 0, 1, 2, 0, 0} 이 나왔다.

블로그를 참고한 대로 풀어보면

처음의 0 idx 는 비교하지 않는다.

다음으로 aa 를 접두사 접미사로 구별하기 위해 보면