단순 문자열 검색 알고리즘
- 문자열 검색 알고리즘이란 S에서 패턴 P를 찾는 알고리즘이다. 가장 쉬운 방법은 다음과 같다.
int search(string S, string P)
{
int len_S = S.length();
int len_P = P.length();
for(int i=0;i<len_S;i++)
{
for(int j=0;j<len_P;j++)
{
if(S[i+j]!=P[j])
{
break;
}
if(j==len_P-1)
{
return i;
}
}
}
return -1;
}
- 이렇게 하면 최악의 경우
(len_S*len_P)만큼의 시간이 걸리게 된다. 이를 단축시키는 알고리즘을 생각해낸게 Knuth, Morris, Prett라는 사람들이다.
KMP
-
문자열 알고리즘 문제가 나오면 해법으로 KMP가 가장 먼저 떠오르는
우리에게 친숙한(?)알고리즘이지만 정작ctrl-c+ctrl-v의 편리함으로 인해 나같이 게으른 사람의 머리에는 잘 남지 않는 알고리즘이다.간단히 정리하자면 KMP는 접두사와 접미사를 활용하는 알고리즘이다.
-
여기 문자열 ABAACABABAABAC가 있다.
| i | 부분문자열 | 접두사&접미사가 일치하는 길이 |
|---|---|---|
| 0 | A | 0 |
| 1 | AB | 0 |
| 2 | ABA | 1 |
| 3 | ABAA | 1 |
| 4 | ABAAC | 0 |
| 5 | ABAACA | 1 |
| 6 | ABAACAB | 2 |
| 7 | ABAACABA | 3 |
| 8 | ABAACABAB | 2 |
| 9 | ABAACABABA | 3 |
| 10 | ABAACABABAA | 4 |
| 11 | ABAACABABAAB | 2 |
| 12 | ABAACABABAABA | 3 |
| 13 | ABAACABABAABAC | 0 |
접두사와 접미사가 문자열 탐색과 무슨 상관이 있을까 싶지만
처음에 나왔던 단순 문자열 검색 알고리즘을 떠올려보자.
문자열 ABCDABCDABD에서 ABCDABD라는 패턴 P를 찾고 싶다.
접두사와 접미사가 중첩되는 길이를 저장하는 Nested라는 배열을 만들어보자
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| P | A | B | C | D | A | B | D |
| Nested | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
-
첫번째 알고리즘의 경우
ABCDABCDABD ABCDABD ABCDABD ABCDABD ABCDABD ABCDABD ABCDABD ABCDABD
이런 식으로 전체 탐색을 하게 되지만
- KMP의 경우
ABCDABCDABD
ABCDABD
ABCDABD
이렇게 불필요한 비교를 줄일 수 있다.
그럼 대망의 함수를 작성해보자.
1.먼저 Nested 배열을 만들어보자
vector<int> make_nested(string P)
{
int idx = 0;
int len_P = P.length();
vector<int>nested(len_P);
for(int i=1;i<len_P;i++)
{
while(j>0)
{
if(P[i]==P[idx])
{
break;
}
idx = nested[idx-1];
}
if(P[i]==P[idx])
{
idx++;
nested[i] = idx;
}
else
{
nested[i] = 0;
}
}
return nested;
}
우리는 이제 어떤 문자열 S에 대해서도 nested 배열을 구할 수 있는 함수를 만들었다.
2.이를 활용하여 KMP 알고리즘을 완성해보자
vector<int> KMP(string S, string P)
{
int idx = 0;
int len_S = S.length();
int len_P = P.length();
vector<int>nested = make_nested(P);
vector<int>ans;
for (int i = 0; i < len_S; i++)
{
while (idx > 0)
{
if (S[i] == P[idx])
{
break;
}
idx = nested[idx - 1];
}
if(S[i]==P[idx])
{
if (idx == len_P - 1)
{
ans.push_back(i - (len_P - 1));
idx = nested[idx];
}
else
{
idx++;
}
}
}
return ans;
}