初探—KMP模式匹配算法

KMP算法思想：

普通的字符串匹配算法S主串必须要回溯。但回溯就影响了效率。

改进的地方也就是这里，我们从P 串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。

next数组的含义：

T串各个位置的j值的变化定义为一个数组next

“当匹配到S[i] != P[j]的时候有 S[i-j…i-1] = P[0…j-1]. 如果下面用k 去匹配，则有P[0…k-1] = S[i-k…i-1] = P[j-k…j-1]。得到 P[0…k-1] = P[j-k…j-1];

next[j]=Max{ "p1...pk-1"="Pj-k+1...Pj-1"}

 1 void CkmpDlg::get_next(String T, int* next) //根据String T子串，求next[] 数组
 2 {
 3     int i,j;
 4     i=1;
 5     j=0;
 6     next[1]=0;
 7     while(i<T[0])
 8     {
 9         if(j==0 || T[i]== T[j])//T[i]表示后缀单个字符，T[j]表示前缀的单个字符，如何相同，各自后移。   
10         {
11             ++i; 
12             ++j;
13             if(T[i]!=T[j])
14                next[i]=j;
15             else
16                 next[i]=next[j];
17         }
18         else
19             j=next[j];
20     }
21 
22 }

get_next() 的求解：T 既是主串，又是模式串。未完待续....