POJ 3461 Oulipo KMP练习

题目链接

题目很长，其实就是字符串匹配。

所以，权当练习 KMP

#include <cstdio>
#include <cstring>
#define MB 10101
#define MA 1000100
char a[MA],b[MB];
int next[MB];
void prekmp(char* b) {
next[0]=-1;
int j=-1;
for ( int i(1); b[i]; i++) {
while ( j!=-1 && b[i]!=b[j+1]) j=next[j];
if ( b[i]==b[j+1] ) j++;
next[i]=j;
}
}
int kmp(char *a,char *b) {
int j=-1,ans=0;
for ( int i(0); a[i]; i++) {
while ( j!=-1 && a[i]!=b[j+1] ) j=next[j];
if (a[i]==b[j+1]) j++;
if (!b[j+1]) {
ans++;
j=next[j];
}
}
return ans;
}
int main() {
int T;
freopen(“in.txt”,“r”,stdin);
for (scanf("%d\n",&T); T–;) {
scanf("%s\n%s\n",b,a);
memset(next,0,sizeof(0));
prekmp(b);
printf("%d\n",kmp(a,b));
}
return 0;
}