作者jessica1338 (茶)
看板b98902HW
标题Re: [资演] 双班-failure function
时间Fri Nov 5 18:32:48 2010
※ 引述《jenny2921 (耶)》之铭言：
: ya~我发现了还不错的投影片所以PO上来跟大家分享唷~
: http://algorithm.cs.nthu.edu.tw/~ds/material/KMP.pps
: 然後顺便贡献上几个练习题~=ˇ=
: 不过底下的答案都是我自己写的~有错欢迎指证~
: a b c d e f g
: -1 -1 -1 -1 -1 -1 -1
: a b c a b c
: -1 -1 -1 0 1 2
: a b a b a b a c
: -1 -1 0 1 2 3 4 -1
: a b z a b c a b z a b z
: -1 -1 -1 0 1 -1 0 1 2 3 4 2
: a b z a b a b z a b z
: -1 -1 -1 0 1 0 1 2 3 4 2
: a b z a b z a b z a b
: -1 -1 -1 0 1 2 3 4 5 6 7
: a b z a b z a b c a b
: -1 -1 -1 0 1 2 3 4 -1 0 1
: 最後再贴一下我写的很弱的code(羞)
: #include<stdio.h>
: #include<string.h>
: int main()
: {
: char str[82];
: int fNum[82];
: while(scanf("%s",str)==1){
: int i;
: for(fNum[0]=-1,i=1;i<strlen(str);i++){
: int index=fNum[i-1]+1;
: while(str[index]!=str[i]){
: index--;
: if(index==-1)break;
: index=fNum[index]+1;
: }
: fNum[i]=index;
: }
: for(i=0;i<strlen(str);i++)printf("%3c",str[i]);
: printf("\n");
: for(i=0;i<strlen(str);i++)printf("%3d",fNum[i]);
: printf("\n");
: }
: return 0;
: }
: 建议大家有空也可以自己写写看~~就会完全确定自己搞懂没了!!:)
有监於原PO这麽热心
我也来分享一个recursive写法
有BUG的话概不负责喔XD
#include <stdio.h>
char find[100];
int f[100];
int failure(int index,char c)
{
if(index==0&&c!=find[0])
{
return -1;
}
if(find[f[index-1]+1]==c)
{
return f[index-1]+1;
}
return failure(f[index-1]+1,c);
}
int main()
{
int f1;
while(scanf("%s",find)==1)
{
f[0]=-1;
for(f1=1;find[f1]!=0;f1++)
{
f[f1]=failure(f1,find[f1]);
}
for(f1=0;find[f1]!=0;f1++)
{
printf("%3c ",find[f1]);
}
printf("\n");
for(f1=0;find[f1]!=0;f1++)
{
printf("%3d ",f[f1]);
}
printf("\n");
}
return 0;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.240.141.128