1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int KMP(vector<int> a, vector<int> b) {
a.insert(a.begin(), 0); b.insert(b.begin(), 0);
vector<int> next(b.size());
for(int l = 0, r = 2; r < b.size(); r ++) {
while(l != 0 && b[r] != b[l+1]) l = next[l];
if(b[r] == b[l+1]) l ++;
next[r] = l;
}
int ans = 0;
for(int i = 1, j = 0; i < a.size(); i ++) {
while(j && a[i] != b[j+1]) j = next[j];
if(a[i] == b[j+1]) j ++;
if(j == b.size()-1) {
ans ++; j = next[j];
}
}
return ans;
}
|