作者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