KMP(Knuth-Morris-Pratt Algorithm)
KMP 문자열 탐색 알고리즘
KMP(Knuth-Morris-Pratt) 문자열 탐색 알고리즘은 문자열 내에서 부분 문자열(패턴)을 효율적으로 탐색하기 위해 사용된다.
단순히 하나씩 비교하게 된다면 문자열의 길이를 n, 찾고자 하는 패턴의 길이를 m이라고 할 때, 시간 복잡도가
이 되어버리기 때문에 거의 모든 백준 내의 문제에서 시간 초과가 나게 된다.
이를 해결하기 위한 방법이 KMP, 이미 일치한 정보를 활용하여 중복되는 비교를 피하여 시간복잡도를
수준으로 줄일 수 있다.
KMP은 두 가지 단계로 나눌 수 있다.
- 전처리 단계
- 탐색 단계
1. 전처리 단계 - pi 배열 만들기
pi 배열은 접두사 = 접미사인 최대 길이를 저장한다.
예를 들어 문자열이 “ABABAC”일 경우
pi = [0, 0, 1, 2, 3, 0]이 된다.
아래는 주어진 문자열 s의 pi 배열을 만드는 코드이다.
// cpf = compute prefix function
vector<int> cpf(string s) {
int m = s.size();
vector<int> pi(m, 0);
int j = 0;
for(int i = 1; i < m; i++) {
while(j > 0 && s[i] != s[j]) {
j = pi[j-1];
}
if(s[i] == s[j]) {
pi[i] = ++j;
}
}
return pi;
}2. 탐색 단계 - 문자열에서 패턴 찾기
위에서 구한 pi 배열로 “ABABABABAC”에서 “ABABAC”가 어디있는지 찾아보자.
먼저 처음 시행이다.
5번째 까지 일치하나 마지막 문자가 일치하지 않는다.
ABABAC 내부에서 ABA가 반복 되므로 다음 시행에서는 앞의 ABA는 비교할 필요가 없다.
두 번째 시행이다.
패턴 : A B A B A C
텍스트의 3~5번째 문자와 패턴의 1~3번째 문자가 일치한다는 것은 이미 알고있기 때문에 비교할 필요가 없다. 그러므로 텍스트의 6번째 문자와 패턴의 4번째 문자부터 비교를 시작한다. 텍스트의 8번 째 문자와 패턴의 6번째 문자가 일치하지 않는다.
세 번째 시행이다.
패턴 : A B A B A C
마찬가지로 텍스트의 5~7번 문자와 패턴의 1~3번째 문자가 일치한다는 것은 이미 알고 있기에 패턴의 4번째 문자부터 비교를 시작해 나간다. 완전히 일치하므로 KMP가 종료된다.
아래는 KMP알고리즘을 구현한 코드이다.
vector<int> KMP(string text, string pattern) {
vector<int> result;
vector<int> pi = pi(pattern);
int n = text.size();
int m = pattern.size();
int j = 0;
for(int i = 0; i < n; i++) {
// 현재 문자가 일치하지 않는 동안,
while(j > 0 && text[i] != pattern[j]) {
// 이전까지 일치한 접두사 길이를 따라 점프하며 비교
j = pi[j - 1];
}
if(text[i] == pattern[j]) {
if(j == m - 1) { // 일치하는 경우
// 패턴이 시작된 위치 저장
result.push_back(i - m + 1);
// 다음 매칭을 위해 점프
j = pi[j];
} else { //계속 비교
j++;
}
}
}
return result;
}KMP알고리즘은 CPF함수와 KMP함수 둘 다 사용하여 문제를 해결한다.
예시) 백준 #4354 문자열 제곱
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> cpf( const string& p) {
int len = p.size();
vector<int> pi(len, 0);
int j = 0;
for(int i = 1 ; i < len ; i++ ){
while(j > 0 && p[i] != p[j]) j = pi[j-1];
if(p[i] == p[j]) pi[i] = ++j;
}
return pi;
}
int solve(const string& s) {
vector<int> pi = cpf(s);
int len = s.size();
int p = len - pi[len-1];
if(len%p == 0) return len/p;
else return 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while(1) {
string s;
cin>>s;
if(s == ".") break;
cout<<solve(s)<<"\n";
}
}