5
HDU1686 Oulipo（KMP）
source link: https://arminli.com/hdu1686/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1686 Oulipo（KMP）
March 29, 2016
KMP 裸题，求子串出现的次数。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int nextt[10010];
void preKMP(char x[], int m, int kmpNext[]){
int i, j;
j = kmpNext[0] = -1;
i = 0;
while(i<m){
while(-1!=j && x[i]!=x[j])
j = kmpNext[j];
if(x[++i] == x[++j])
kmpNext[i] = kmpNext[j];
else kmpNext[i] = j;
}
}
int KMP_Count(char x[], int m, char y[], int n){
int i, j;
int ans = 0;
preKMP(x,m,nextt);
i = j = 0;
while(i<n){
while(-1!=j && y[i]!=x[j])
j = nextt[j];
i++;
j++;
if(j>=m){
ans++;
j = nextt[j];
}
}
return ans;
}
int main(){
//freopen("a.txt", "r", stdin);
int n; cin >> n;
while(n--){
char a[10010], b[1000005];
scanf("%s %s", a, b);
cout << KMP_Count(a, strlen(a), b, strlen(b)) << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK