KMP 알고리즘(Knuth-Morris-Pratt Algorithm)
이 알고리즘을 이해를 쉽게 하기 위해서는 KMP알고리즘에서의 접두사와 접미사를 알고가야한다.
예시 하나로 설명하고 넘어가겠다.
ex)
apple이라는 문자열이 주어졌다.
<apple의 접두사>
1, a
2, ap
3, app
4, appl
5, apple
총 5개의 접두사를 갖는다.
<apple의 접미사>
1, e
2, le
3, ple
4, pple
5, apple
총 5개의 접미사를 갖는다.
위의 예시로 접두사, 접미사 설명은 충분할 것으로 본다.
이제 KMP 알고리즘 원리를 알아보겠다.
우리가 기존에 아는 완전 탐색법(브루트 포스법)으로 문자열 찾을 때는 문자를 일일이 비교를 해가면서 찾았다.
책의 한 페이지에서 문자열을 찾는다고 하면 우린 책을 텍스트라하며 찾고자하는 문자열을 패턴이라한다.
브루트 포스법에 대한 짤막한 설명
브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계에서 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검사를 수행한다.
여기서 이전단계에서 검사했던 결과를 버리는것이 매우 비효율적이다. 검사 결과를 통해 다음결과에서 어떤결과가 나올지 알 수 있는데 버린다는건 큰 낭비이다.
※ KMP법은 접두사와 접미사를 통해 이전결과를 버리지않고 사용하여 다음결과에서 효율적인 실행을 할 수 있다.
Target text: 문자들
Pattern: 찾고자하는 문자열
LPS: 접두사를 이용해 문자열 찾을 수 있게 해주는 table
위의 사진과 같이 ACA가 두 개가 보인다. 만일 현재의 자리에서 텍스트와 패턴이 일치하지않는다면 패턴을 한 칸 오른쪽으로 미뤄서 비교하는것보다 뒤에 있는 ACA자리까지 패턴을 미뤄서 비교하는게 불필요한 실행을 줄일 수 있을것이다.
따라서 KMP 알고리즘의 핵심은 불필요한 계산을 방지하기위해 텍스트에 존재하는 패턴의 접두사를 찾아 그 부분에서만 탐색할 수 있게 해주는것이다.
파이썬을 통해 KMP 알고리즘 구현
LPS를 만드는 법을 알아보자.
LPS는 우리가 접두사(혹은 접미사)를 통해서 텍스트와 패턴을 비교할 곳을 찾아준다.
우선 2개의 동일한 패턴을 비교해준다.
A: 패턴 ABCABA
B: 패턴 ABCABA
2개의 패턴을 패턴1[인덱스 0]과 패턴2[인덱스 1]에 맟줘 비교할 것이다. LSP는 인덱스0자리는 -를 넣어준다.
패턴1 ABCABA
패턴2 ABCABA
LPS -0 문자 B와 문자 A는 일치하지않다. 0 기입
패턴1 ABCABA
패턴2 ABCABA
LPS -00 문자 C와 문자 A는 일치하지않다. 0 기입
패턴1 ABCABA
패턴2 ABCABA
LPS -001 문자 A와 문자 A는 일치한다. 1 기입
패턴1 ABCABA
패턴2 ABCABA 이전 단계에서 0이 아닌 숫자가 들어갔기에 아래 패턴을 이동시키지 않는다.
LPS -0012 문자 B와 문자 B는 일치한다. 2기입
패턴1 ABCABA
패턴2 ABCABA
LPS -00120 문자 A와 문자 C는 일치하지않다. 0기입
패턴1의 모든 문자열과 비교를 마췄기에 LSP 테이블완성.
시간복잡도: O(텍스트의 길이 + 패턴의 길이)
최악의 시간복잡도: O(텍스트의 길이)
위에 파이썬 코드에 적용하면 KMP알고리즘을 사용할 수 있다. 실제 프로그램에서 별로 사용하지않는다. 이상으로 KMP알고리즘 설명을 마치겠다.
'Algorithm' 카테고리의 다른 글
| [알고리즘] 벨만 포드(최단경로에 음수 간선이 있을 때) (0) | 2022.02.12 |
|---|---|
| [알고리즘] 다익스트라 (0) | 2022.02.08 |
| [알고리즘] 에라토스테네스의 체 (0) | 2022.02.07 |
| [알고리즘] 투 포인터 (0) | 2022.02.06 |
| [알고리즘] 보이어･무어법 (0) | 2022.01.23 |
