KMP 알고리즘

일반적인 알고리즘의 경우 O(문자열 길이 * 패턴의 길이)의 시간복잡도가 소요되어, 문자열이 길거나 패턴이 긴 경우 비효율적인 코드를 작성할 수 있다.

이를 해결하기 KMP 알고리즘이 등장했다.

KMP 알고리즘이란, Knuth, Morris, Prett이 만든 알고리즘으로, 문자열 탐색을 수행할 때 O(N+M)의 시간복잡도로 문제를 해결할 수 있도록 도와준다.

접두사 Prefix 접미사 Suffix

1. KMP 알고리즘은 접두사와 접미사의 개념을 활용한다.

• Prefix 예)
  Apple --> A Ap App Appl Apple

• Suffix 예)
  Apple --> e le ple pple Apple

2. pi[i]는 길이가 i인 문자열이 있고, 0~i까지의 부분 문자열 중 Prefix == Suffix가 될 수 있는 부분 문자열 중에서 가장 큰 길이
   (Prefix가 0~i 까지의 부분 문자열과 같으면 안됨)

• 예1) ABAABAB

i	  sub_srting	pi[i]
-------------------------
0	   	A			0
1	   	AB			0
2	   	ABA			1
3		ABAA		1
4		ABAAB		2
5		ABAABA		3
6		ABAABAB		2

• 예2) AABAA

i	  sub_srting	pi[i]
-------------------------
0	   	A			0
1	   	AA			1
2	   	AAB			0
3		AABA		1
4		AABAA		2

---

단순한 비교 알고리즘의 경우 다음과 같이 수행한다.

1번 수행 시

0 1 2 3 4 5 6 7 8 9 10
A B C D A B C D A B E
A B C D A B E  <-- ! 다름 !! (6번째 인덱스가 다름!!)

2번 수행 시

0 1 2 3 4 5 6 7 8 9 10
A B C D A B C D A B E
  A B C D A B E  <-- ! 다름 !! (1번째 인덱스가 다름!!)

이러한 과정에서, 1번 인덱스가 틀렸다는 정보만 사용한다.

즉, 1번 수행했을 때, 0~5번 인덱스가 일치한다는 정보를 활용하지 않았다는 뜻이다.

해당 정보를 활용하는 경우, 아래와 같이 사용할 수 있다.

0 1 2 3 4 5 6    7 8 9 10 11
A B C D A B C(i) D A B E  E			# i = 텍스트의 현재 비교위치
        A B C(j) D A B E  			# j =   패턴의 현재 비교위치

위 과정이 가능한 이유는, 패턴 ABCDAB의 Prefix와 Suffix가 AB로 일치하기 때문이다.

또한, Prefix와 Suffix가 일치하는 최대 길이이므로, ABCDABE의 pi[i] = 2.

---

참고1
참고2