KMP裸题
(极限5分钟A题)
/**
freopen("in.in", "r", stdin);
freopen("my.out", "w", stdout);
*/
//// /////////////////////////////
#include <cstdio>
#include <cstring>
const int N = ; int nex[N];
char s[N], p[N]; int main() {
while(scanf("%s", s)) {
if(s[] == '#') break;
scanf("%s", p);
int ans = ;
nex[] = ;
for(int i = , j = ; i < strlen(p); i++) {
while(j && p[i] != p[j]) {
j = nex[j - ];
}
if(p[i] == p[j]) j++;
nex[i] = j;
}
for(int i = , j = ; i < strlen(s); i++) {
while(j && s[i] != p[j]) {
j = nex[j - ];
}
if(s[i] == p[j]) j++;
if(j == strlen(p)) {
ans++;
j = ;
}
}
printf("%d\n", ans);
}
return ;
}
AC代码