[문자열 매칭 알고리즘 #1] KMP 알고리즘

특정 패턴 A를 문자열 B에서 찾는 알고리즘이다.

 

무식하게 풀수 있는 방법도 존재한다.

 이중 for문을 돌면서 첫글자와 일치하는 곳에서 패턴을 돌면서 확인하는 방법이 존재하나

O(N*M) 이기 때문에 매우 비효율적이다.

 

중복되는 부분을 건너띄고자 KMP 알고리즘은 개발되었다.

 

접두사            접미사     A     B     C      A

접두사           접미사 A     B     C     B     A

접두사                         접미사 A     B      C     A     B     A     B     C

먼저 접미사, 접두사를 이용하면 중복되는 부분을 해결할 수 있다.

 

예시를 들어보자

 

문자열(P): A B C D A B C D A B D E

패턴(T): A B C D A B D

 

라고 가정해보자.

 

      1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
      | | | | | | X
P : [ A B C D A B D ]
      1 2 3 4 5 6 7

6번까지는 일치하지만 C와 D가 일치하지 않는다.

그러나 가만 보면 패턴의 5, 6은 문자열의 1, 2와 일치하는 것을 알 수 있다.

 

따라서, T의 2번부터가 아니라 T의 5번부터 찾기를 실시하면 될것 같다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
              | | | | | | |
P :         [ A B C D A B D ]
              1 2 3 4 5 6 7

 

이를 쉽게 구하기위해 반복되는 부분을 미리 저장하면 된다.

 

0번 인덱스는 패스하고 1번부터 확인하여 같은 +1, 다르면 0을 저장한다.

이제 표를 구했으니 문자열에서 패턴을 찾아보자.

 

브루트포스 방법처럼 처음에 일일히 찾기를 시작한다.

그러다 서로 다른 부분을 발견한다.

(Parent문자열) i=6와 (Pattern) j=6가 다르다.

그러면 저장했던 Border의 6-1부터 j를 다시 시작한다.

 

만약 i=6과 j=3이 서로 다르면 다시 테이블에서 Border[2-1] 부터 j를 시작하면 된다.

 

이를 구현하는 문제를 풀어보자.

https://www.acmicpc.net/problem/1786

1786번: 찾기