該樓層疑似違規已被系統折疊?隱藏此樓查看此樓
我自己寫的KMP算法:
int?nt[256];
void?get_next1(char*?T,?int?next[],?int?tlen)
{
int?i?=?0;
int?j?=?1;
next[0]?=?-1;
while(?j?
{
if?(?T[i]?==?T[j]??)
{
next[j]?=?0;
i++;
}
else
{
next[j]?=?i;
i?=?0;
}
j++;
}
}
int?Index_KMP1(char*?S,?char*?T,int?slen,?int?tlen)
{
int?i=0,?j=0;
while(?j?
{
if(?j==-1?||?S[i]?==?T[j]?)
{
i++;?j++;
}
else
{
j?=?nt1[j];
}
}
if(?j?==?tlen?)
{
return?i-j;
}
else
{
return?-1;
}
}
int?main(int?argc,?char*?argv[])
{
char?ch[]?=?"aaaaa";
int?len?=?(int)strlen(ch);
get_next1(ch,?nt1,?len);
for(int?i=0;?i
{
printf("%d[%c]=%d\n",?i,?ch[i],?nt1[i]);
}
char?sch[]?=?"abaavaaaaaab";
//char?sch[]?=?"aawsdvddfabcdabceabcdfdwdasd";
int?slen?=?(int)strlen(sch);
int?ret?=?Index_KMP1(sch,?ch,?slen,?len);
if(ret?!=?-1)
{
char*?tmp?=?sch?+?ret;
printf("%d,?%s\n",?ret,?tmp);
}
else
printf("not?find\n");
return?0;
}
我發現在數據結構的書中,用的SString類型,它的第一位是該字符的長度,所以和我們平時所需要的KMP算法不太兼容。
有什么問題,可以發到我的郵箱:bobyuworker@126.com