-
Notifications
You must be signed in to change notification settings - Fork 1
/
kmp.cpp
157 lines (143 loc) · 3.85 KB
/
kmp.cpp
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*
KMP算法
g++ kmp.cpp -o kmp -std=c++11
test case 1:
BBC ABCDAB ABCDABCDABDE
ABCDABD
blog: https://zeqiang-lai.github.io/Algorithms/kmp.html
date: 2020-1-21
*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 优化
vector<int> get_next2_opt(const string& p) {
vector<int> next(p.size());
next[0] = -1;
int i=0, k=-1;
while(i < p.size() - 1) {
if(k == -1 || p[i] == p[k]) {
i++; k++;
if(p[k] != p[i]) next[i] = k;
else next[i] = next[k];
} else { k = next[k]; }
}
return next;
}
vector<int> get_next2(const string& p) {
vector<int> next(p.size());
next[0] = -1;
int i=0, k=-1;
while(i < p.size() - 1) {
if(k == -1 || p[i] == p[k]) {
i++; k++;
next[i] = k;
} else { k = next[k]; }
}
return next;
}
// 不要使用这个, 这种优化写法是错的
// Do not use this version, it is incorrect optimization.
vector<int> get_next_opt(const string& p) {
vector<int> next(p.size());
next[0] = -1;
for(int i=1;i<p.size();i++){
int k=i-1;
while(k!=0 && p[i-1] != p[next[k]]) k=next[k]; // 先找出"OK"的前缀后缀
// 直接这样优化是不行的
if(p[i] != p[next[k]+1]) next[i] = next[k] + 1;
else next[i] = next[next[k]+1];
}
return next;
}
vector<int> get_next(const string& p) {
vector<int> next(p.size());
next[0] = -1;
for(int i=1;i<p.size();i++){
int k=i-1;
while(k!=0 && p[i-1] != p[next[k]]) k=next[k]; // 先找出"OK"的前缀后缀
next[i] = next[k] + 1;
}
return next;
}
vector<int> get_next_vanilla(const string& p) {
vector<int> next(p.size());
next[0] = -1;
for(int i=1; i<p.size(); i++) {
int n_match = 0;
// 枚举所有可能的相同前缀后缀
for(int k=1; k<i; k++) {
bool ok = true;
for(int j=0; j<k; j++) {
if(p[j] != p[i-k+j]) ok = false;
}
if(ok == true) n_match = k;
}
next[i] = n_match;
}
return next;
}
int find_kmp(const string& s, const string& p, vector<int>(*_get_next)(const string&)) {
vector<int> next = _get_next(p);
for(int x : next) {
cout << x << " ";
}
cout << endl;
int i=0, j=0;
while(i < s.size() && j < p.size()) {
if(s[i] == p[j]) { i++; j++; }
else {
if(next[j] == -1) i++; // 如果p[0]都不匹配, i要加1了
else j = next[j];
}
}
if(j == p.size()) return i-j;
else return -1;
}
int find_vanilla(const string& s, const string& p) {
int pos = -1;
bool ok = true;
for(int i=0; i<s.size(); i++) {
ok = true;
for(int j=0; j<p.size(); j++) {
if(s[i+j] != p[j]) { ok = false; break; }
}
if(ok) { pos = i; break; }
}
return pos;
}
int find_vanilla2(const string& s, const string& p) {
int i=0, j=0;
while(i < s.size() && j < p.size()) {
if(s[i] == p[j]) { i++; j++; }
else { i=i-j+1; j=0; }
}
if(j == p.size()) return i-j;
else return -1;
}
string getline(int buffer_size=1024) {
char buffer[buffer_size];
cin.getline(buffer, buffer_size);
string str(buffer);
return str;
}
void printResult(string source, string pattern, int pos) {
if(pos == -1) {
cout << "could not find """ << pattern << """ in " << source << endl;
} else {
cout << "found """ << pattern << """ at " << pos << endl;
cout << source << endl;
for(int i=0; i<pos; i++) cout << " ";
cout << pattern << endl;
}
}
int main()
{
string source = getline();
string pattern = getline();
// int pos = find_vanilla2(source, pattern);
int pos = find_kmp(source, pattern, get_next2_opt);
printResult(source, pattern, pos);
return 0;
}