[資演] 雙班-failure function

[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;
}

建議大家有空也可以自己寫寫看~~就會完全確定自己搞懂沒了!!:)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.136
※ 編輯: jenny2921       來自: 140.112.30.136       (11/05 15:12)
推 SoranoKid:認真用心推!!
推 yudi1991:推