KMP 알고리즘

보통 문자열 안에서 패턴을 찾는 알고리즘을 만들때

가장 쉽게 생각해볼 수 있는 것은

문자 하나하나마다 패턴과 일치하는지 체크하는 방법일겁니다.

 

그런데 위 방법은 당연하게도 시간 복잡도가 O(패턴의 길이 * 문자열의 길이)가 되므로

굉장히 느립니다..

그렇다면 빠른 속도로 패턴을 찾아여 할때는 어떻게 해야할까..

 

KMP 알고리즘

패턴 테이블을 이용한 kmp의 경우

문자열을 단 1회만 순회 하면서도 패턴을 찾아내는 굉장히 빠른 알고리즘입니다.

 

브루트포스로 문자열 검색 알고리즘을 짜면 O(N * M)의 시간이 걸리는 가장 큰 이유는

이전에 나온 문자들과 이후에 나올 문자들을 기억하지 않는다는데에 있습니다.

따라서 중복된 비교가 일어날 수 밖에 없는데

KMP의 경우 패턴 테이블을 만듦으로서 이전에 비교한 문자들과

이후에 나올 문자들에 대해 대비를 할 수 있기 때문에

O(N + M)의 속도로 검색이 가능해집니다.

 

KMP 알고리즘의 동작 방식

문자열 - abcdabcabb

패턴 - abcab

 

테이블 생성

실패 함수를 이용하여 테이블을 생성합니다

실패 함수는 문자열을 검색할때 불일치가 발생하면 패턴의 처음으로 돌아가 다시 탐색하는 것이 아닌

중복되는 부분으로 돌아가 효율적인 탐색이 가능하게끔 만들어줍니다

vector<int> makeTable(string Pattern) 
{
        vector<int> table(Pattern.size(), 0);

        for (int tail = 1, head = 0; tail < Pattern.length(); tail++)
        {
                while (head > 0 && Pattern[tail] != Pattern[head])
                        head = table[head - 1];

                if (Pattern[tail] == Pattern[head])
                        table[tail] = ++head;
        }
     
        return table;
}

 

 

a	b	c	a	b
head	tail
0	0	0	0	0

 

head와 tail을 비교하여 같으면 해당 index table에 번호를 기입함

위의 경우는 조건에 맞지 않으므로 넘깁니다.

 

a	b	c	a	b
head		tail
0	0	0	0	0

위의 경우에도 조건에 맞지 않으므로 넘깁니다.

 

a	b	c	a	b
head			tail
0	0	0	0	0

위의 경우에는 head 인덱스의 문자와 tail 인덱스의 문자가 서로 같으므로 조건에 해당합니다.

 

a	b	c	a	b
	head		tail
0	0	0	1	0

다시한번 tail이 ++가 되고

 

a	b	c	a	b
	head			tail
0	0	0	1	2

head 인덱스의 문자와 tail 인덱스의 문자가 서로 같으므로 조건에 해당합니다

따라서 위와같이 " 0 0 0 1 2 " 로 테이블이 완성이 됩니다.

 

 

패턴 테이블을 이용한 문자열 탐색

void KMP(string str, string pattern)
{
        vector<int> table = makeTable(pattern);
        int parentSize = str.size();       // abcaabcabb [ 10 ]
        int patternSize = pattern.size();  // abca [ 4 ]
        
        int j = 0;
        for (int i = 0; i < parentSize; i++)
        {
                while (j > 0 && str[i] != pattern[j])
                {
                        j = table[j - 1];
                }
                if (str[i] == pattern[j])
                {
                        if (j == patternSize - 1)
                        {
                                cout << i - patternSize + 2 << "에서 패턴을 찾았습니다." << endl;
                                j = table[j];
                        }
                        else
                        {
                                j++;
                        }
                }
        }
}

 

문자열	a	b	c	a	a	b	c	a	b	b
	i
패턴	a	b	c	a	b
	j
패턴 테이블	0	0	0	1	2

초기상태

 

문자열	a	b	c	a	a	b	c	a	b	b
		i
패턴	a	b	c	a	b
		j
패턴 테이블	0	0	0	1	2

str[tail]과 pattern[j] 의 문자가 서로 같으니 j에 +1을 해줍니다

반복문이 1회 돌아서 i도 +1이 됩니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
			i
패턴	a	b	c	a	b
			j
패턴 테이블	0	0	0	1	2

str[i]과 pattern[j] 의 문자가 서로 같으니 j에 +1을 해줍니다

반복문이 1회 돌아서 i도 +1이 됩니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
				i
패턴	a	b	c	a	b
				j
패턴 테이블	0	0	0	1	2

str[i]과 pattern[j] 의 문자가 서로 같으니 j에 +1을 해줍니다

반복문이 1회 돌아서 i도 +1이 됩니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
					i
패턴	a	b	c	a	b
					j
패턴 테이블	0	0	0	1	2

str[i]과 pattern[j] 의 문자가 서로 같으니 j에 +1을 해줍니다

반복문이 1회 돌아서 i도 +1이 됩니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
					i
패턴	a	b	c	a	b
		j
패턴 테이블	0	0	0	1	2

str[i]과 pattern의 문자가 서로 다르니 j= table[j- 1]로 바꿔줍니다

j는 1이 되고 다시한번 while문 안에서 i과 비교합니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
					i
패턴	a	b	c	a	b
	j
패턴 테이블	0	0	0	1	2

str[i]과 pattern의 문자가 서로 다르니 j= table[j- 1]로 바꿔줍니다

j는 0이 되고 while문이 종료됩니다.

 

문자열	a	b	c	a	a	b	c	a	b	b
						i
패턴	a	b	c	a	b
		j
패턴 테이블	0	0	0	1	2

str[i]과 table[j]의 문자가 서로 같으니 j에 +1을 해줍니다. 

반복문이 1회 돌아서 i도 + 1

 

문자열	a	b	c	a	a	b	c	a	b	b
							i
패턴	a	b	c	a	b
			j
패턴 테이블	0	0	0	1	2

str[i]과 table[j]의 문자가 서로 같으니 j에 +1을 해줍니다.

반복문이 1회 돌아서 i도 + 1

 

문자열	a	b	c	a	a	b	c	a	b	b
								i
패턴	a	b	c	a	b
				j
패턴 테이블	0	0	0	1	2

str[i]과 table[j]의 문자가 서로 같으니 j에 +1을 해줍니다.

반복문이 1회 돌아서 i도 + 1

 

문자열	a	b	c	a	a	b	c	a	b	b
									i
패턴	a	b	c	a	b
					j
패턴 테이블	0	0	0	1	2

str[i]과 table[j]의 문자가 서로 같으니 j에 +1을 해줍니다.

반복문이 1회 돌아서 i도 + 1

 

str[i]와 table[j]의 문자가 서로 같은 상태에서

j가 패턴테이블 끝까지 왔다는건 패턴을 찾았다는 의미가 됩니다