25/01/14 백준일지 with KMP
백준 문제풀이
문자열 탐색 알고리즘
길이가 \(n\)인 문자열에서 길이가 \(m\)인 문자열을 naive하게 찾는 시간복잡도는 \(O(nm)\)이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
int search(string s, string t){
for(int i = 0; i < s.size(); i++){
bool tf = true;
for(int j = 0; j < t.size(); j++){
if(s[i + j] != t[j]){
tf = false;
break;
}
}
if(tf) return i;
}
return -1;
}
시간이 매우 길게 걸린다. 여기서 최적화를 한 것이 앞으로 나올 KMP 알고리즘이다.
KMP란?
Knuth-Morris-Prett의 이름 앞글자를 따서 지어진 알고리즘이다.
상단의 알고리즘은 \(O(nm)\)의 시간복잡도이지만 KMP는 \(O(n + m)\)의 획기적인 시간복잡도를 가지고 있다. 그럼 이를 어떻게 구현하는지 알아보자.
생각의 흐름
naive한 탐색 방법은 우리가 어느정도까지 일치함을 파악해도 이를 이용할 수가 없다. \(s[i]\)에서 \(t\)의 앞 세 문자가 일치한다고 하더라도 다음 글자가 틀렸다면 그저 버리는 값이 될 뿐이다. KMP에서는 이 버려지는 값인 부분 일치 정도를 이용하여 중복연산을 제거한다.
해당 칸에서 연산을 해야하는 여부는 어떻게 판단할까? \(s\)의 a부터 b까지의 부분 문자열을 앞으로 \(s[a, b]\)라 하자. \(s[i, i + n] == t[0, n]\)일 떄 다음칸에서의 판단이 필요한지 케이스를 나누어 살펴보자.
\(s[i + 1, i + n] != t[0, n - 1]\)
우리는 \(t\)가 \(s\)의 내부에 있는지를 파악해야 한다. 따라서 이 경우는 판단할 필요가 없다.
\(s[i + 1, i + n] == t[0, n - 1]\)
이 등식이 성립한다면 자연스럽게 \(s[i + 1, i + n] == t[0, n - 1] \rightarrow t[0, n - 1] == t[1, n]\)이 성립함을 알 수 있다. 대우를 적용한다면 \(t[0, n - 1] != t[1, n]\) 일 떄는 문자열 일치 여부를 판단 할 필요가 없다는 결론이 나온다.
이를 통해 우리는 \(t\)의 접두사와 접미사의 일치 여부로 다음 칸을 판단할지 하지 않을지를 알 수 있다. 이 접미사의 일치 여부를 배열로 표현한 것을 실패 함수 라고 부른다.
실패 함수
\(f(k) =\){\(t[0, k]\)에서 접두사와 접미사의 가장 긴 일치길이}이며, 코드는 다음과 같다
1
2
3
4
5
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
KMP
\(i\)에서 \(n(n < t.size() - 1)\)개의 문자열이 중복되었다면 \(i + 1\)칸에서는 \(f(n - 1)\)값의 여부를 판단하고 건너뛸지 말지를 판단 가능하게 한다.
실패함수를 포함한 KMP를 완성해보자
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
vector<int> ans;
for(int i = 0, j = 0; s[i];){
if(s[i] == t[j]){
i++; j++;
if(j == t.size()) ans.push_back(i - j + 1);
}else if(j) j = f[j - 1];
else i++;
}
1786
무난한 KMP사용 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int f[1001000];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string s, t; getline(cin, s);
getline(cin, t);
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
vector<int> ans;
for(int i = 0, j = 0; s[i];){
if(s[i] == t[j]){
i++; j++;
if(j == t.size()) ans.push_back(i - j + 1);
}else if(j) j = f[j - 1];
else i++;
}
cout << ans.size() << "\n";
for(int l : ans) cout << l << " ";
return 0;
}
1305
실패함수를 이용하여 최소길이 구하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int f[1001000];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; string t;
cin >> n >> t;
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
cout << t.size() - f[t.size() - 1];
return 0;
}
9792
최장 중복 문자열을 구한 뒤, 그 내부에 특정 문자열이 있는지를 판단하는 문제.
n이 1500 이하이니 믿음을 갖고 브루트포스하여 최장 중복 문자열을 구하고 KMP를 쓰자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int f[2000];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<string> sv;
while(n--){
string t; cin >> t;
string cur = "";
for(int idx = 0; idx < t.size(); idx++){
memset(f, 0, sizeof(f));
for(int i = 1, k = 0; t[i + idx];){
if(t[i + idx] == t[k + idx]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
int tmp = 0;
for(int i = 0; i < t.size() - idx; i++){
if(f[tmp] < f[i]) tmp = i;
}
if(cur.size() < f[tmp]){
cur = t.substr(idx, f[tmp]);
}
}
sv.push_back(cur);
}
int m; cin >> m;
while(m--){
memset(f, 0, sizeof(f));
string t; cin >> t;
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
int cnt = 0;
bool tf = false;
for(string s : sv){
for(int i = 0, j = 0; s[i];){
if(s[i] == t[j]){
i++; j++;
if(j == t.size()){
tf = true;
cout << cnt << " ";
break;
}
}else if(j) j = f[j - 1];
else i++;
}
cnt++;
}
if(!tf) cout << "-1";
cout << "\n";
}
return 0;
}
9120
그냥 KMP쓰자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int f[1000100];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--){
string t, s; cin >> t >> s;
memset(f, 0, sizeof(f));
for(int i = 1, k = 0; t[i];){
if(t[i] == t[k]) f[i++] = ++k;
else if(k) k = f[k - 1];
else i++;
}
int cnt = 0;
for(int i = 0, j = 0; s[i];){
if(s[i] == t[j]){
i++; j++;
if(j == t.size()) cnt++;
}else if(j) j = f[j - 1];
else i++;
}
cout << cnt << "\n";
}
return 0;
}