KMP 알고리즘 이해하기

KMP 알고리즘 개념

 

설명하기에 앞서 자주 쓰일 용어를 먼저 정의하도록 하겠습니다.

T : 찾으려는 대상이 포함된 본문 텍스트

P : 찾으려는 대상(패턴)

begin :  T와 P 비교가 시작되는 인덱스(0 <= begin < T.length)

comparing :  T와 P를 비교하기 위한 P 위의 인덱스(0 <= comparing < P.length)

current :  T와 P를 비교하기 위한 T 위의 인덱스(0 <= current < T.length)

matched : T와 P를 비교하면서 일치된 문자수

 

일반적인 문자열 탐색의 경우에서 위 그림처럼 비교 도중 전체가 일치하지 않을때  begin 인덱스를 하나씩 올려서 다시 comparing = 0 으로 초기화해서 다시 검색을 수행합니다. T의 문자마다 P의 길이만큼의 연산이 수행되므로 시간 복잡도는 O(NM)가 됩니다.

만약 T와 P의 길이가 충분히 길어서 100만 정도 된다면 작업을 완료하기엔 시간이 너무 오래걸립니다.

 

KMP 알고리즘은 이 문제점을 O(N+M)의 복잡도로 해결한 알고리즘 입니다.

어떻게 복잡도를 줄였을까요? 개념 자체는 전혀 어렵지 않습니다. 오히려 우리는 이미 이 개념을 직관적으로 알고 있습니다.

 

간단한 예를 통해서 살펴볼까요?

 T의 임의의 부분에서 P와 대조중이라고 가정합니다. 명명하기 쉽도록 문자열 위의 번호를 기입했습니다. 

만약 4번째 인덱스에서 문자열이 맞지 않는다는걸 알았습니다. 이제 우리의 문제는 위의 정보를 바탕으로 효율적인 검색이 가능하도록 하는 next_begin 값을 찾는 겁니다. 

 

위의 정보를 바탕으로 next_begin을 찾는다면 어떤 값으로 해야될까요? 직관적으로 2번임을 짐작할 수 있습니다. 

단순하게 "어? 빨간상자 문자열의 앞뒤가 같으니 앞부분을 뒷부분에 일치시켜서 대조를 시작하면 되겠다" 생각할 수 있습니다.

 

그럼 이런 질문이 나올 수 있습니다. "어차피 2번으로 옮겨도 4번에서 또 틀릴텐데 왜 2번으로 옮기나요?"

위의 한번의 대조에서 얻은 정보는 4번 위치의 T 문자가 D가 아니라는 정보입니다. 임의의 T 부분에서 4번 자리에 A가 나올수도 있습니다. 만약 위의 T가 ABABA 라면 2번을 next_begin으로 시작하면 답을 찾을 가능성이 있습니다. 

 

이처럼 일치한 문자열의 앞,뒤에서 일치하는 부분이 있을 때 일치시켜 begin 값을 스킵하는 것이 KMP 알고리즘입니다.

좀 더 구체적으로 표현하자면 일치한 문자열의 접두사를 접미사부분으로 이동시켜 begin값을 스킵한다라고 표현할 수 있겠네요.

 

추가) 위의 예에서 next_begin을 이동시켰다면 틀린 부분에서부터 검색을 시작합니다. AB 부분은 이미 일치하므로 검색할 필요가 없겠죠?

---

pi 값

 

이전 설명에서 일치한 문자열의 접두사와 접미사를 이용해서 next_begin 값을 결정할 수 있다고 말했습니다.

좀 더 다듬어서 표현하자면 next_begin 값은 아래의 빨간상자 문자열에서 일치하는 접두사와 접미사 최대 길이에 의존합니다.

(이제부터 편의를 위해 해당 문자열에서 일치하는 접두사와 접미사의 최대 길이를 pi라고 부르겠습니다.)

 

왜 최대길이일까요? 다시 아래의 예를 살펴보겠습니다. 

 

 

위의 예에서 next_begin을 구해보겠습니다. 위의 일치된 문자열은 AAAA 입니다.

AAAA 에서 나올 수 있는 접두사는 A, AA, AAA 입니다. (자기 자신 AAAA는 제외됩니다. 이를 포함하면 구현시 무한 루프를 돌 수 있기 때문입니다.)

P에서 접두사를 A로 선택할 경우 일치하는 접미사는 가장 맨 뒤에 있는 A이므로 next_begin은 가장 맨 뒷자리입니다.

같은 이유로 AA를 선택하면 화살표 중간자리, AAA를 선택하면 가장 앞 화살표자리입니다.

 

어떤 자리를 정해야할지 감이 오셨을겁니다. 바로 가장 앞자리(즉 일치하는 접두사의 최대길이)를 선택해야합니다. 뒷자리를 선택하면 답이 될 가능성이 있는 앞자리도 건너뛰게 되기 때문입니다.

 

자, 이제 일치하는 문자열의 pi값이 next_begin을 결정한다는 것을 알았습니다. 그렇다면 pi값은 어떻게 구해야될까요?

이 부분도 상당히 중요합니다. 아무 생각없이 P의 접미사 부분이 뒷부분과 일치하는지 일일이 체크한다면 시간복잡도는 O(M^2)의 복잡도가 되어버립니다(0 <= i < P.length인 모든 P[0~i]에 대해서 수행해야되기 때문) .  P의 길이가 길어진다면 제한시간 내에 검색할 수 없습니다.

 

그래서 pi값을 구할때도 KMP 알고리즘을 이용해야합니다.  

---

pi값 구하기 

 

보통 P의 부분 문자열에 대한 pi값은 사전에 미리 계산해 배열에 저장해둡니다.

이번에도 간단한 예를 통해서 구하는 방법에 대해 살펴보겠습니다.

 

P가 ABABA라는 문자열이라고 가정합니다. 그리고 같은 P를 1번 인덱스부터 시작해 비교를 시작합니다.

방식은 위에서 사용한 KMP 방식(접미사, 접두사를 이용한 스킵)을 사용합니다.

 

첫번째 비교에서는 일치한 문자없이 바로 실패했습니다. 이런 경우 그냥 next_begin = begin+1 하고 다음 비교를 시작합니다.

두번째 비교에서는 일치하는 문자열이 있습니다. 여기서 살짝 중요합니다. 목적이 P의 부분 문자열의 pi값을 찾는 것이므로 위의 예와는 목적이 다릅니다. 그래서 다른 관점으로 볼 필요가 있습니다.

 

두번째 비교에서 begin은 2이고 current도 2에서 시작합니다.  current(위쪽 P의 인덱스)와 comparing(아래쪽 P의 인덱스)을 하나씩 증가시킬때마다 일치 문자열이 하나씩 추가되고 있습니다. 

current=2 일때 일치하는 문자열은 A입니다. 위쪽 P[0~2] 문자열을 보면 일치한 문자들이 접미사가 되고 있는 패턴이 보이시나요?

위처럼 일치할 때마다 pi 값을 배열에 저장해두면 됩니다.

---

마무리

 

P의 pi값 배열을 미리 구해놨다면 이제 다시 돌아가 문자열 검색을 시작하면 됩니다. 

원하던 문자열을 찾았을 때, 문자열이 일치하지 않을 때와 같은 상황에서 pi값과 current나 begin, comparing등의 인덱스를 이용해서 next_begin 값을 구해나가면 됩니다. 

 

뭔가 마무리가 엉성한 것같아 찜찜하기도 하지만, 사실 개념은 이게 답니다. 나머지는 이 개념을 구현과 맞물리도록 하는 것인데 이것까지 담으려하면 오히려 단순한 개념이 더 어렵게 느껴질것 같기도 하고, 또 글이 너무 길어질 것 같기도해서 예제 링크를 남기는 것으로 마무리합니다.  

 

백준 1786 : 찾기

 

최대한 자세히 내용을 담으려했는데, 전달이 잘 됐는지 모르겠네요. 

조금이나마 누군가에게 도움이 됐길 바라며~