[알고리즘/문자열] KMP 알고리즘 - C++

KMP 알고리즘

(Knuth-Morris-Pratt Algorithm)

KMP 알고리즘 (수행시간 : O(N))
 : 문자열 탐색에 있어 겹치는 부분을 미리 탐색해 불필요한 검색을 하지 않도록 점프시키는 알고리즘.

일반적인 문자열 탐색 알고리즘을 사용하는 경우, 글의 길이가 M, 패턴의 길이가 N이라고 하면 수행시간은 O(MN)이 된다.

이때 어떻게 하면 이러한 중복 문자열 탐색을 줄일 수 있을까 하여 나온 방법이 KMP 알고리즘이다.

 

수행 원리

  문자열을 탐색할 때 겹치는 부분이 있는데, 일반적인 탐색의 경우 이를 무시하고 다시 처음부터 탐색을 진행하게 된다.

  KMP는 미리 탐색한 이러한 겹치는 문자열을 어떻게 활용할지를 고안하여 만들어낸 알고리즘이다.

  우리는 접두사(Prefix)와 접미사(Suffix)의 중복을 확인 할 것이다.

 

  abcabdabc라는 탐색이 필요한 문자 패턴이 있다고 하자.

 

문자	겹치는 수
a	0
ab	0
abc	0
abca	1
abcab	2
abcabd	0
abcabda	1
abcabdab	2
abcabdabc	3

  이와 같이 접두사와 접미사의 일치부분이 나타나며, 이 부분은 점프해주도록 구현을 할 것이다.

 

실패 함수

  KMP 구현에 앞서 접두사와 접미사의 매칭 구조를 배열로 저장하도록 만드는 함수.

  매칭에 실패하였을 때 얼마나 건너뛸지를 지정하는 함수이다.

  i는 1번 인덱스에, j는 0번 인덱스에 놓고 i와 j를 비교하여 일치하는 갯수를 찾는 방법이다.

  패턴은 String pt라고 정의한다.

 

  Step 1. j=0, i=1에 배치, 배열의 인자는 모두 0으로 초기화.

0	1	2	3	4	5	6	7	8
j	i
a	b	c	a	b	d	a	b	c
0	0	0	0	0	0	0	0	0

  Step 2. i의 인덱스와 j의 인덱스 비교. pt[i]≠pt[j]이므로 i만 한 칸 앞으로 이동시켜준다.

0	1	2	3	4	5	6	7	8
j		i
a	b	c	a	b	d	a	b	c
0	0	0	0	0	0	0	0	0

  Step 3. i의 인덱스와 j의 인덱스 비교. 마찬가지로 pt[i]≠pt[j]이므로 i만 한 칸 앞으로 이동시켜준다.

0	1	2	3	4	5	6	7	8
j			i
a	b	c	a	b	d	a	b	c
0	0	0	0	0	0	0	0	0

  Step 4. 비교. pt[i]=pt[j]이므로 table[i] = ++j를 해준다. (현재 일치값 + 1을 한 값을 저장) 이후 i도 한 칸 이동시켜준다.

0	1	2	3	4	5	6	7	8
	j			i
a	b	c	a	b	d	a	b	c
0	0	0	1	0	0	0	0	0

  Step 5. 비교. pt[i]=pt[j]이므로 table[i] = ++j를 해준다. 이후 i도 한 칸 이동시켜준다.

0	1	2	3	4	5	6	7	8
		j			i
a	b	c	a	b	d	a	b	c
0	0	0	1	2	0	0	0	0

  Step 6. 비교. pt[i]≠pt[j]이므로 j값을 이전 테이블의 j위치로 이동시켜준다. ( j = table[j - 1] ) i는 그대로 한 칸 이동시켜준다.

0	1	2	3	4	5	6	7	8
j						i
a	b	c	a	b	d	a	b	c
0	0	0	1	2	0	0	0	0

  Step 7 ~ Step 9. 앞서 설명한 방법과 같은 방법으로 진행한다. 결과는 아래와 같다.

0	1	2	3	4	5	6	7	8
		j						i
a	b	c	a	b	d	a	b	c
0	0	0	1	2	0	1	2	3

  실패 함수는 이와 같은 방식으로 진행된다.

  코드는 아래와 같다.

vector <int> fail(string pt)
{
    vector <int> table(pt.size(), 0);
    int j = 0;
    for (int i = 1; i < pt.size(); i++)
    {
        while (j > 0 && pt[i] != pt[j])
        {
            j = table[j - 1];
        }
        if (pt[i] == pt[j])
        { 
            table[i] = ++j;
        }
    }
    return table;
}

 

KMP 함수

  실패 함수가 구현되었으니 이제 KMP를 구현하면 되는데, 원리와 구현 방법은 거의 유사하다.

  단지 비교하는 것이 패턴 자체가 아닌, 패턴과 텍스트와의 비교로 바뀐 것 뿐이다.

  string txt = "abcaabcab", string pt = "abcab" 를 예로 들어보자.

 

  Step 1. i와 j를 모두 0에 둔다. 

0	1	2	3	4	5	6	7	8
a	b	c	a	a	b	c	a	b
a	b	c	a	b

  Step 2. i와 j가 서로 일치하므로 둘 다 한 칸 이동시켜준다.

0	1	2	3	4	5	6	7	8
a	b	c	a	a	b	c	a	b
a	b	c	a	b

  Step 3 ~ Step 4. 마찬가지로 일치하므로 계속 이동시켜준다.

0	1	2	3	4	5	6	7	8
a	b	c	a	a	b	c	a	b
a	b	c	a	b

  Step 5. 인덱스 4에서 불일치가 났으므로, 바로 일치했던 직전 점의 실패함수 값으로 j를 이동시킨다. ( j = table[j - 1] )

0	1	2	3	4	5	6	7	8
a	b	c	a	a	b	c	a	b
a	b	c	a	b

  패턴 "abcab"의 실패 함수 테이블은 {0, 0, 0, 1, 2}이므로 j = table[4 - 1] = table[3] = 1이 된다.

 

  Step 6. 일치하므로 i와 j를 둘 다 한 칸씩 이동시켜준다.

0	1	2	3	4	5	6	7	8
a	b	c	a	a	b	c	a	b
a	b	c	a	b

  이와 같은 방식으로 진행해주면 되며, 전부 일치하여도 추가로 동일한 값이 있을 수 있으므로 j값을 옮겨주어야 한다.

  코드는 아래와 같다.

void KMP(string txt, string pt)
{
    vector <int> table = fail(pt);
    // 패턴에 대한 실패함수 작성
    int txtsize = txt.size();
    int ptsize = pt.size();
    int j = 0;
    for (int i = 0; i < txtsize; i++)
    {
        while (j > 0 && txt[i] != pt[j])
        {
            j = table[j - 1];
            // 일치하지 않았을 때 일치하던 직전 인덱스의 테이블값으로 이동
        }
        if (txt[i] == pt[j])
        {
            if (j == ptsize - 1)
            // j의 인덱스가 0부터 시작하므로, 패턴 사이즈보다 1보다 작은 위치에 j가 있으면 모두 일치
            {
                j = table[j];
                // 일치하므로 현재 인덱스의 테이블값으로 이동
                // 일치하는 갯수, 일치하는 위치 등을 확인하고 싶으면 여기에 추가 함수 작성
            }
            else
            {
                j++;
            }
        }
    }
}