星期二, 11月 18, 2008

[知識] KMP Alogorithm

KMP演算法為一個利用Failure Function(Prefetch Table)的字串比對演算法。時間複雜度為O(Pattern Length+Target Length)。

此演算法最麻煩的部分在於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值+1]比。相同則Failure值+1,不同時則再跟P[0]比,相同則為0,再不同時則為-1。

沒有留言: