[알고리즘] KMP

[알고리즘 소개]

전체 문자열에서 부분 문자열을 효율적으로 찾는 알고리즘.

 

---

[코딩 방법 - 실패 함수]

1. 실패 테이블 만들기. table[i]는 0부터 i까지에서 접두사, 접미사가 겹치는 최대 길이
2. 부분 문자열 pattern을 1부터 N까지 for문으로 순회, j는 0에서 시작
3. j > 0 이거나 pattern[i] != pattern[j]이면 j = table[j - 1] 반복
   (이전까지 계속 맞았다면 table[j - 1]에는 0이 아닌 값이 들어 있을 것이고 접미사 부분까지 맞았음이 확인됐으므로 처음부터 다시 비교할 필요가 없이 접미사와 같았던 접두사 부분까지는 생략하고 확인 가능)
4. pattern[i] == pattern[j] 이면 table[i] = ++j

---

[코딩 방법 - KMP]

1. 전체 문자열 parent를 0부터 N까지 순회, pattern을 확인할 j도 0부터 시작
2. j > 0이거나 parent[i] != pattern[j]이면 j = table[j - 1] 반복
   (실패 테이블을 짜던 것과 같은 흐름. parent[i - 1]까지와 pattern[j - 1]까지 달랐다면 parent[i]와 pattern[0]을 비교하면 되는 것이고 같았다면 접미사 부분까지도 맞았으므로 접미사와 같은 접두사 생략)
3. pattern[i] == pattern[j] 이고 j < patternSIze - 1이라면 ++j
4. pattern[i] == pattern[j] 이고 j == patternSIze - 1이라면 부분 문자열을 찾은 것.

---

[시간 복잡도]

$O(N + M)$

 

---

[참고]

왜 이렇게 해야하는지 이해가 안 간다면 아래 예시를 손으로 직접 해볼 것

•  KMP: ABCABABCABCABABCD  ABCABABCD
• 실패 함수: ABCABAABCABC

---

[공부용 링크]

https://yiyj1030.tistory.com/495