会python真的可以为所欲为0(回)
359天前
这里还有人吗1(回)
544天前这里还有人吗0(回)
544天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
769天前到处都是羊，不想上班0(回)
849天前
鸽子
0(回)
853天前
hdu-1686 Oulipo(kmp).rar(免费下载)[0 次下载]/* |
2016年4月28日10:27:36 |
kmp |
注意重复的也算 |
p：AZA |
t：AZAZAZA |
ans = 3; |
*/ |
#include<stdio.h> |
#include<string.h> |
const int maxn = 1e6 + 5; |
char p[10005]; |
int next[10005]; |
char t[maxn]; |
void makenext() |
{ |
int m = strlen(p); |
next[0] = 0; |
for(int q = 1,k = 0;q < m;q++) |
{ |
while(k > 0 && p[q] != p[k]) |
k = next[k-1]; //跳到上一个前缀 |
if(p[q] == p[k]) |
k++; |
next[q] = k; |
} |
} |
int kmp() |
{ |
int ans = 0; |
int m = strlen(p); |
int n = strlen(t); |
for(int i = 0,q = 0;i < n;i++) |
{ |
while(q > 0 && p[q] != t[i]) |
q = next[q-1]; |
if(p[q] == t[i]) |
q++; |
if(q == m) |
{ |
ans++; |
q = next[q-1]; //如果重复的不算的话，q = 0;和上面的k = next[k-1];比较看一下 |
} |
} |
return ans; |
} |
int main() |
{ |
int T; |
scanf("%d",&T); |
while(T--) |
{ |
scanf("%s",p); |
scanf("%s",t); |
makenext(); |
printf("%d\n",kmp()); |
} |
return 0; |
} |
/* |
3 |
BAPC |
BAPC |
AZA |
AZAZAZA |
VERDI |
AVERDXIVYERDIAN |
1 |
3 |
0 |
*/ |
hdu-1686 Oulipo(kmp).rar(免费下载)[0 次下载]
