[22.01.06] KMP 알고리즘

 

# KMP 알고리즘

 

문자열을 찾는 데 사용되는 알고리즘

ex) 웹 브라우저 상에서 현재 페이지에 포함되어 있는 특정 단어를 찾고 싶을 때 ctrl + f 를 사용

 

- 일반적으로 주어진 글에서 원하는 문자열을 찾고 싶다면 어떤식으로 설계해야 할까?

 

ABC라는 단어를 찾고싶다면 우선 A로 시작하는 곳을 찾고 그 뒤가 B인지 판단, B가 맞다면 뒤가 C인지를 판단하면 되지 않을까?

이렇게 한다면 앞에서부터 무작정 3글자씩 비교해보는 것보다는 효율적일 것 같다. 하지만 찾고자하는 문자가 길수록, 찾고자하는 문자열의 뒤쪽에서 오류가 날 수록 원하는 단어를 찾는데는 오랜 시간이 걸릴 것이다.

: 이때의 시간 복잡도는 원본 문자열의 길이가  N, 탐색 문자열의 길이가 M일때 O(NM)으로 나타난다.

 

-> 시간 복잡도를 O(N+M)으로 획기적으로 줄일 수 있는 KMP 알고리즘 (커누스-모리스-프랫 알고리즘, Knuth, Morris, Pratt)

 

접두사와 접미사

 

KMP 알고리즘에 대해 이해하기 위해 우선 접두사와 접미사에 대한 이해가 필요하다.

접두사(prefix) , 접미사(suffix)

 

접두사란 문자열에서 맨 앞에서부터 한 글자씩 ( 1~ ) 증가시켰을 때 나오는 문자의 배열을 뜻하고

접미사는 반대로 문자열의 맨 뒤에서부터 한 글자씩 증가시켰을 때 나오는 문자의 배열을 의미한다.

 

pi배열

 

문자열이 주어졌을 때 접두사 = 접미사가 되는 문자열을 찾고 이 중 가장 긴 것의 길이를 구해준다.

ABAB 일경우

부분 문자열을 확인해보았을 때

A -> X

AB -> X

ABA -> 접두사 A = 접미사 A가 되고 이때의 길이는 1이다.

ABAB -> 접두사 AB = 접미사 AB가되고 이때의 길이는 2이다.

 

 

 

KMP 알고리즘의 아이디어

 

문자열이 불일치하는 경우 기존에 비교했던 정보를 활용해 더 많은 인덱스를 건너 뛰고 탐색할 순 없을까?

-> 건너 뛰기 위해서는 건너 뛰려는 위치의 시작단어가 찾으려 하는 단어의 시작 단어와 동일해야 할 것이다!!

=> 건너 뛸 때 찾는 탐색 문자열의 앞 부분과 찾는 탐색 문자열의 뒷 부분이 일치해야 한다!!

 

따라서 찾으려하는 탐색 문자열의 접두사와 접미사를 미리 구해 얼마나 건너 뛸 수 있는 지를 알 수 있게 된다.

 

- 그래서 접두사와 접미사, Pi 배열을 어떻게 사용해 문자열을 구하는 건데?? 

 

Pi 배열은 일반적으로 pi[i]로 0~len(문자열의길이)-1 까지로 i를 받아 부분 문자열에서의 접두사=접미사가 될 수 있는 문자열의 최대길이를 구해준다.

따라서 예를들어 만약 6글자인 문자열을 찾고 싶은데 첫 체크부분에서 5번째 문자에서 오류가 발생했을 경우, 맞은 부분의 길이는 4이고 이때의 pi[3] (0부터 시작) 에 해당하는 숫자가 있을 것이다 (2라고 가정). 이 때 len(맞는문자열) - pi[문자열길이-1] 만큼을 건너뛰고 계산하면 되는 것이다.

 

ex) ABABCABC문자열이 있는데 

      ABABD를 찾고싶다! -> ABAB는 맞고 이때의 pi[3]은 2이다. 이때 맞는 문자열의 길이는 4 -  pi[3]의 값 2 = 2 만큼 건너뛰어 거기서부터 다시 찾으면 되는 것!!

 

또한 위 상황과 같은 경우에는 건너뛰고 난 뒤에 다시 A부터 비교할 필요 없이 AB가 같음을 알기 때문에 B뒤에서부터 비교를 시작하면 조금이라도 계산 과정을 줄일 수 있다.

 

 

#############################################################################

( 코드 삽입 예정 ) 여기까지 이해하는데에도 오래걸려서 코드에 대한 공부는 이후에 이어서 진행하겠다..

#############################################################################

 

 

- 하나씩 다 해보는 알고리즘은 브루트 포스(Brute Force)라고 부른다고 한다. 노가다

 

find_str = 'long'
text = 'shortlongpen'


for i in range(len(text)-len(find_str)): # 끝에서 4번째 전까지
    if text[i:i+4] == find_str:
        print("찾는 문자열의 위치는 :", i+1, "~", i+5, "번 째까지 입니다.")
        break

: 인덱스를 하나씩 비교하는 코드는 아니지만 이런식으로 진행하겠다~ 싶은 코드를 한번 짜보았다. 물론 범용성을 위해서는 i+4대신 len(find_str)을 넣는게 좀 더 좋을 것 같다. ( 밑에 있는 숫자도 마찬가지 )