问下严蔚敏数据结构的串

august

里面一章说的  模式匹配的改进算法

给出的例子是这样的

j           |  1 2 3 4 5 6 7 8

模式  | a  b a a b c a c

next[j] | 0  1  1 2 2 3 1 2

next[1] 是先赋0值的.


之后给出了求 next值的函数
如下所示;

2. void get_next(SString T,int &next[])
3. {
4.     //求模式串T的next函数值并存入数组next
5.     i = 1;  next[1] = 0;  j = 0;
6.     while(i<T[0]) //T[0]这里应该是指串T的长度
7.     {
8.         if(j==0 || T[i] == T[j])
9.         {
10.             ++i;++j;
11.             next[i] = j;
12.         }
13.         else
14.             j = next[j];
15.     }
16. }

复制代码

不过按这个算法,得到的 next[j]的值, 到了 next[4] 就不对了,
按上面的例子到了 next[4] 应该是等于 2  ,但按这算法是等于1
请问这是怎么回事呢?

shawind

没看过这本书，数据结构方面的东西，看着就头大....

august

看了她的视频还是一样的算法,但算出来确实不对....

lw

KMP，建议G搜索，印象有
直接说明，恐用词晦涩，反而误导

dbshy

百度百科搜索KMP算法，那里的讲解比较详细 = =