참고 블로그:
https://pearlluck.tistory.com/581
[python] 문자열매칭. KMP 알고리즘 (백준16916, 백준1786)
단어검색 (문자열매칭) 요구사항 - 워드안에서 Ctrl+F하는 것 처럼, 검색한 단어들이 있는 모든 위치를 전부 알려줘! - 단어사전에 단어가 수만개, 문서길이가 수천개 - 문서는 띄어쓰기가 없거나
pearlluck.tistory.com
KMP 알고리즘을 이해하는데 위 블로그를 참고했다.
한 문자열 M이 다른 문자열 N이랑 매치되거나 포함되는지 확인하는 알고리즘으로 쉽게 생각해볼 수 있는건 N에서 M의 시작점을 옮겨가며 매치되는지 확인하는 것이다. 하지만 이와 같은 방법으로는 O(MN)의 시간복잡도를 가진다.
KMP 알고리즘을 사용하면 접두사와 접미사가 같은 최대 개수를 사용해서 이미 같다고 판단된 부분은 스킵해면서 비교해나간다. 위 그림에서 abcdabc까지 같고 그 뒤로 틀렸다면, 한칸씩 이동하는게 아니라 abcd의 뒤까지 바로 이동해서 다시 비교를 시작하는 것이다. KMP 알고리즘을 이용하면 O(M+N)의 시간만에 원하는 답을 구해낼 수 있다.
그러기 위해서는 먼저 N 문자열에 M 문자열이 포함되는지 확인하는 과정을 거친다고 할 때, M 문자열에 대한 pi 배열을 만들어야 한다. 이때 pi 배열은 접두사 접미사의 최대 개수를 한글자씩 더해가면서 확인하는 것이다. 위 그림만으로는 이해가 어려워서 따로 그림을 그려보았다.
pi 배열을 이용해서 두 문자열을 비교하는 과정도 pi 배열을 구하는 과정과 똑같다.
