?? kmp算法中求next數(shù)組.txt
字號(hào):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//KMP算法中求next數(shù)組
/*
輸入
ababa
cabababababac
輸出
0 1 1 2 3 4 0 0 0 0
3
*/
void getnext(char *T,int *next)
{
next[1]=0;
int j=1,k=0;
while(j<=strlen(T))
{
if((k==0)||T[j-1]==T[k-1])
{
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}
int main()
{
char T[10],T1[15],count=0;//T表示模版,T1表示被比較字符串
int next[11],i,j;
for(i=1;i<11;i++)
next[i]=0;
scanf("%s",T);
scanf("%s",T1);
getnext(T,next);
printf("next數(shù)組為:\n");
for(i=1;i<11;i++)
printf("%2d",next[i]);
printf("\n");
for(i=0;i<strlen(T1);)
{
for(j=0;j<strlen(T);)
{
if(T1[i]!=T[j]&&j==0)
i++;
else if(T1[i]!=T[j])
{
j=next[j+1]-1;
}
else
{
i++;
j++;
}
}
if(j==strlen(T)) count++;
}
printf("%d\n",count);
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -