此演算法最麻煩的部分在於Failure Function的建立。程式碼如下:
void fail2(char *pat)
{
int cnt,pos=0;
int n=strlen(pat);
T[0]= -1;
for(pos=1; pos=0)
{
cnt=T[cnt];
if(pat[pos] == pat[cnt+1])//現在的比對文字 與前一格的Failure Value+1相同
T[pos] = cnt+1;
else
T[pos]=-1;
}
}
手動建立要訣為:(P指Pattern,T指Prefetch Table)
1. 首先(即P[1],因為T[0]必為-1)跟P[0]比對,相同為0(即P[0]+1),不同為-1。
2. 接著,繼續比對時如果前面Failure值為-1,則跟P[0]比,如果不是則跟P[Failure
沒有留言:
張貼留言