KMP(Knuth Morris Pratt) algorithm

용어 : prefix , suffix

1. 핵심 개념

두개의 문자열이 일치하고 있는 경우

이 문자열을 비교하는 경우 몇 칸을 이동하면 suffix 와 prefix 가 일치할까?

이는 문자열

abcabc
에서 suffix 중에서 최대 prefix 를 구하는 문제이다. 이 것이 패턴을 전처리 하는 과정이다. KMP 방법은 찾고자 하는 pattern 을 조작하여 속도를 높이는 방법이다.

몇 가지 예를 들어 보면

이를 구하는 방법이 분류 3 의 패턴의 전 처리 방법이다.

2. KMP 방법은 어떻게 속도를 높이나?

KMP 알고리즘은 찾고자 하는 패턴을 미리 전 처리하여 이러한 정보를 구한 후 한 칸이상을 움직여 비교하여 속도를 높이는 방법이다.

예를 들어,


3. pattern 에 대한 전처리는 ?

패턴이 아래와 같다면

a b c a b c a a

구하고자 하는 결과 배열은 아래와 같다.

문자 위치 0 1 2 3 4 5 6 7
패턴 문자 a b c a b c a a
인덱스 -1 -1 -1 0 1 2 3 0

-1 인 경우 일치하는 부분이 없다.

설명---

패턴의 suffix , prefix 가 두개의 사각형모양으로 일치한다고 하자.

다음 진행에서 두가지 경우가 발생할 수 있다.

  1. 일치하는 경우(그림에서는 동그라미 , 동그라미)

    이 경우는 간단히 오른쪽 동그라미에 왼쪽의 동그라미의 위치를 저장하면 된다.

  2. 일치하지 않는 경우(그림에서는 동그라미 , 사각형)

    이 경우는 네모위치에 동그라미가 있다고 생각 후 같은 방식으로 생각하면 된다. (이 부분 조금 생각해야 합니다)

    그림으로 설명하면

    • 그림에서는 한 번 더 접근할 시에 동그라미가 나타나는 경우이다.

      왼쪽의 파란사각형과 오른쪽의 파란사각형의 패턴이 일치

    예를 들어 ,
       
       a b a d ... a b a
       -----       -----
    
    에서 다음 문자로 b 가 오면
       a b a d ... a b a b
       -----       -----
    
    b 와 d 가 같지 않다.

    d 앞에 a 가 있고 이는 0 번째 a 를 가리키고 있으니 0 번째 문자 다음 문자를 보니 b 이므로

    a b a b 의 b 위치에는 두 번째(위치로는 1)를 가리키면 된다.

    ::패턴을 전 처리하는데 필요한 시간 복잡도 : O(n)


[질/답]
[홈으로]  [뒤 로]
[푼 후(0)]