문자열 매칭 알고리즘[2](KMP)[String Searching Algorithm, Knuth-Morris-Pratt]

먼저 이 문제(찾기, 1786)를 먼저 보고 오자. 백준에서 플5문제이고 KMP를 사용해야 되는 이유를 잘 설명해주고 있다.

 

문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 

 

파이썬에서는 kmp 관련 문제가 나오면 정규식(regex, re)으로 찾자^^. 

---

1. KMP 알고리즘 정의

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다.

KMP 알고리즘은 Knuth, Morris, Prett가 만든 문자열 매칭 알고리즘으로 시간복잡도는 O(N+M)으로 무식한 방법 O(NM)보다 매우 빠르다.

사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.

• 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.
• 두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.

 

2. KMP 알고리즘의 개념

찾기-1786(백준)

문제와 같이 텍스트에서 패턴을 찾을 때, 텍스트에서 패턴과 길이가 같은 부분문자열을 모두 확인해보는 방식이 아니라, 전처리 과정을 거친 후 이를 이용해서 점프하면서 찾는다는 원리이다.

전처리 과정을 이해하기 위해서는 접두사(prefix)와 접미사(suffix)를 알아야 된다.

 

<banana의 접두사> : b, ba, ban, bana, banan, banana

<banana의 접미사> : a, na, ana, nana, anana, banana

 

실패함수는 (패턴의)부분문자열 중에서 접두사와 접미사가 같은 가장 긴 길이를 저장한다.

fail 값은 
이전값을 이용해서 구할 수 있다.
0번째 문자와 같으면 길이가 1이다.
다음 글자가 같으면 +1, 같지 않으면 0

 

index	0	1	2	3	4	5	6	7	8
문자열의길이	1	2	3	4	5	6	7	8	9
P[i]	A	B	A	C	A	B	A	B	A
fail[i]	0	0	1	0	1	2	3	2	3

fail[i] 값이 k라면 부분문자열의 길이가 len[i] 라고 할 때
앞부터 k번째 인덱스 전까지와 뒤부터 k번째 인덱스 전까지 같다는 것
즉 len[i+1] 길이의 부분문자열 의 fail[i+1] 값을 구할 때는
p[k]와 추가된 문자(p[i+1])를 구별하면 된다. // k번째 인덱스를 비교하면 된다는 것이다.
이때 같으면 +1, 같지 않으면 0이다. //같지 않다면 일단 0이라고 생각하자.

하지만 중요한 점은 index 7을 확일할때
같지 않아서 fail(7)은 0이 아니다. // 같지 않다면 0이 아닌 경우가 있다.

//index 6에서 fail 값은 가장 긴 값만 저장하기 때문에  3이다. 하지만 문자열 ABACABA에서 접두사, 접미사가 같은건 ABA, A 두개이다. // ABA안에 A가 속해있기 때문에 A만 따로 검사해야한다.

 

ABACABAB

ABACABAB

 

ABA 비교 : ABAC(0123)와 ABAB(4567)는 같지 않다.

A 비교 : AB(01)와 AB(78)는 같다.

 

 

 

fail(6)은 3이므로 len[i]가 3인 부분문자열(ABA) 즉, index가 2일 때 ABA에서 fail(2) =1 이고, AB(01)==AB(78)이므로, 길이가 1개인 fail(7) = fail(2) + 1 = 2이다.

 

 

fail값 구하는 가장 중요한 부분.
길이가 가장 긴것을 저장하기 때문에 더 짧은 것에 대해서도 다 구할 수 있고
다시 이걸 왔다 갔다 하는 방식을 fail값을 구할 수 있다.

 

가장 긴것을 알고 있으면 길이가 짧은 걸 모두 구할 수 있기 때문이다. //이전에 구했기 때문에.

ex) ABCABDABCABEABC의 KMP 구하기

ABCABDABCA
++++--++++
ABCA 길이 4;
하지만 부분 문자 열중에 이전에 구했던.
ABCA 중에서
+--+ 으로 이미 길이가 1인 것을 구해서 같다.

 

이후 답을 구하는 방법은 전처리와 많이 다르지 않다.

 

 

3. KMP 알고리즘 구현

vector<int> preprocessing(string p) {
	vector<int> fail(p.size());
	int m = p.size();
	fail[0] = 0;	//부분문자열의 길이가 1이면 fail값은 0이다.
	int j = 0;
	for (int i = 1; i < m; ++i) {
		while (j > 0 && p[i] != p[j]) j = fail[j - 1]; 		//점프
		if (p[i] == p[j]) {							//문자가 같다면 +1
			fail[i] = j + 1;
			j++;
		}
		else {
			fail[i] = 0;							//문자가 다르다면 0
		}
	}
	return fail;
}

vector<int> kmp(string s, string p) {	//s : 텍스트, p : 패턴
	auto fail = preprocessing(p);		//전처리
	int n = s.size();
	int m = p.size();
	int j = 0;
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		while (j > 0 && s[i] != p[j]) j = fail[j - 1];		//점프
        // 길이가 j인, 즉 0~j-1까지 부분문자열의 fail값.
		if (s[i] == p[j]) {				//문자가 같다면
			if (j == m - 1) {			//p의 마지막 문자까지 전부 같다면
				ans.push_back(i - m + 1);	//텍스트에서 패턴의 시작위치
				j = fail[j];			//(중복이 되어 있을 수도 있으므로)
			}
			else {
				j++;
			}
		}
	}
	return ans;
}

preprocessing에서 수행 시간과 관련된 코드는 아래와 같다.

preprocessing
while (j > 0 && p[i] != p[j]) j = fail[j - 1];

전체적으로 j가 증가하는 횟수는 |P|이기 때문에, 이 부분은 최대 |P|번 j를 감소시킨다.

preprocessing 시간복잡도 : O(|P|)

kmp 시간복잡도 : O(|S|+|P|)

 

4. KMP 관련 문제 풀이

//백준 티어는 높지만 난이도는 높지 않았다 -> 혜자 문제

 

1786 찾기 : https://www.acmicpc.net/problem/1786

#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
#define endl '\n'

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

vector<int> kmp(string s, string p) {
	auto fail = preprocessing(p);
	int n = s.size();
	int m = p.size();
	int j = 0;
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		while (j > 0 && s[i] != p[j]) j = fail[j - 1];
		if (s[i] == p[j]) {
			if (j == m - 1) {
				ans.push_back(i - m + 1);
				j = fail[j];
			}
			else {
				j++;
			}
		}
	}
	return ans;
}

int main(void) {
	string s, p;
	getline(cin, s);
	getline(cin, p);
	auto ans = kmp(s, p);
	cout << ans.size() << endl;
	for (auto a : ans) {
		cout << a + 1 << " ";
	}
}

 

1305 광고 : https://www.acmicpc.net/problem/1305

풀이 : 

광고 문구가 될 수 있는 것중에서 가장 짧은 길이를 찾는 문제.

광고문구가 될 수 있는 가능성을 가진 것은 무엇일까??

(직접 광고문구가 될 수 있는 리스트를 구해보면서 문제 파악)

현재 광고판에 나온 문자열을 포함한
광고판의 문자열의 prefix이다.

즉 답은 L-fail(L)이다.
반복되다가 잘리는 게 있으므로.
마지막에만 일부분이 나올 수가 있는데
그 부분이 fail값과 같은 의미를 가짐.
fail은 가장 긴 값을 넣었음.

즉 전체 길이에서 fail 값을 빼면 가능한 광고의 길이 중 가장 짧은 것을 구할 수 있다.

preprocessing 가 갖는 의미를 잘 파악하자 : 선두와 후미가 겹치는 가장 긴 부분 문자열의 길이.

#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
#define endl '\n'

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

int main(void) {
	string s;
	int n;
	cin >> n >> s;
	auto k = preprocessing(s);
	cout << s.size() - k[s.size() - 1];
}

 

1701 Cubeditor : https://www.acmicpc.net/problem/1701

풀이 : 

어디서부터 시작할지만 정하면 되는 문제.

fail[i] 값의 최댓값을 구하면 된다.
//직접 fail 값을 계산하였을 때.. 보인다.
// abcfaabc
// 0000123
왜냐? 첫 번째부터 시작하는 것과 같았기 때문에
두 번 이상 반복하지 않는다면 값이 채워지지 않기 때문에

하지만 반례가 있다.
fabcabc
000000
이경우
abcabc 도 해보고
~ bc 도 해보는 식으로 첫 부분을 다르게 preprocessing 해서 fail 값을 구하면 된다.

이게 가능한 이유 중 하나는
모든 부분 문자열은 어딘가에서 시작해서 어딘가에서 끝난다.
어떤 suffix의 prefix이다.

시간복잡도
O(|S|^2)

#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <string.h>	//memset
#include <vector>
#include <time.h>
#include <queue>
#include <stack>
#include <cmath>
#include <iostream>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<=(m);i++)
#define si(n) fscanf(in,"%d",&n)
#define NM 1005
#define MOD 1000000009
#define endl '\n'
typedef long long int ll;

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

vector<int> kmp(string s, string p) {
	auto fail = preprocessing(p);
	int n = s.size();
	int m = p.size();
	int j = 0;
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		while (j > 0 && s[i] != p[j]) j = fail[j - 1];
		if (s[i] == p[j]) {
			if (j == m - 1) {
				ans.push_back(i - m + 1);
				j = fail[j];
			}
			else {
				j++;
			}
		}
	}
	return ans;
}

int main(void) {
	
	string s;
	cin >> s;
	
	int ans = 0;
	for (int i = 0; i < s.size(); ++i) {
		string p = s.substr(i, s.size());
		auto tmp = preprocessing(p);
		for (auto a : tmp) {
			if (ans < a) ans = a;
		}
	}
	cout << ans;
	/*
	auto tmp = preprocessing(s);
	for (auto a : tmp) {
		cout << a << " ";
	}*/
}

https://www.acmicpc.net/problem/12104

12104번: 순환 순열

풀이 : 
바이너리 문자열에서 XOR 했을 때, 0이 나오는 순환 순열의 개수를 구하는 문제
XOR
0 0 = 0
0 1 = 1
1 0 = 1
1 1 = 0
XOR은 같을 때 0이 나온다.
즉 두 문자열이 같은지 구별하는 문제
순환 순열의 개수는 N개 구해서 푸는게 아니라
길이가 2N-1인 문자열을 만들어 풀면 되는 문제.
-> S에서 T가 몇개인지 찾는 문제.



https://www.acmicpc.net/problem/13506

13506번: 카멜레온 부분 문자열

풀이 : 

문제에서 요구하는 답은 문자열에서 접두사와 접미사가 같고 두 경우가 아닌 위치에도 등장하는 부분 문자열을 구하는 것이

1)
문자열을 전처리 한 후 큰 순서대로 정렬(패턴 중에서 큰 것 부터)
처음과 일치하며 세번 이상 등장하는 문자열을 출력

2)
fail[n]이 정답이 될 수 있다.
처음과 마지막을 제외하고 fail[n]이 한 번 더 나와야 한다.

fail[n]이 아니라면 fail[fail[n]]은 정답이 될 수도 있다.
이런식으로 계속 검사해본다.