#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int KMP(char a[],char key[],int next[],int i);
int main()
{
char*a;
char*key;
a =malloc(sizeof(char)*220);
key =malloc(sizeof(char)*22);
a[0]=1;
key[0]=1;
int i =0;
char y;
while((y =getchar())!='\n'&& y !=EOF) {
a[++i]= y;
}
i =0;
while((y =getchar())!='\n'&& y !=EOF) {
key[++i]= y;
}
int next[20];
int j, k;
int keyLen;
keyLen =strlen(key)-1;
j =1;
k =0;
next[1]=0;
while(j <= keyLen)
{
if(k ==0|| key[k]== key[j])
{
j++;
k++;
next[j]= k;
}
else
{
k = next[k];
}
}
for(i =1; i <= keyLen; i++)
{
printf("%d,", next[i]);
}
printf("\n");
int index;
index =KMP(a, key, next,0);
int flag =0;
while(index !=0)
{
flag =1;
printf("%d\n", index);
index =KMP(a, key, next, index +1); }
if(flag ==0)
{
printf("-1");
}
return0;
}
int KMP(char a[],char key[],int next[],int i) {
int j =1;
int aLen =strlen(a)-1;
int keyLen =strlen(key)-1;
while(i <= aLen && j <= keyLen)
{
if(j ==0|| a[i]== key[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(j == keyLen +1)
{
return i - keyLen;
}
else
{
return0;
}
}
测试样例：
aaaaaaaaa
a
aaaaaaaaaa
aa
a
a
01122345678909876543112245611231224563534151341513515313111122011223456789098765431122456 11231224563534151341513515313111122
1122
kkkabcdefgabcdefgabcdefkkkkkkkkkkkkkkkkkkkkkkk
abcdefgabcdefgabcdef
10938401705103581035081193510985107051358153-1-351-1318
abcdabcd
abcdefgabcdefgabcdefkkkkkkkkkkkkkkkkkkkkkkk
abcdefgabcdefgabcdef
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议