纠结的kmp

郁闷，书上的居然看不懂，什么乱七八糟的公式，也不知道怎么来的，那怎么办，自己分析呗！！！啊呀呀

 

设： 主串:S,  模式串：T,
 len(s) = ls, len(t) = lt; (ls >= lt)
 S[pos] = x， T[j] = Y；
 X != Y;
 求nex[n]的值；（下面是对nex的定义）
 

假设定义在 nex[j] (0=   {-1，0， k} (0在此集合上的操作：
 1：nex[j] = -1,  ----> cmp( S[pos 1], T[0]);
 2: nex[j] = 0,   ----> cmp( S[pos], T[0]);
 3: nex[j] = k,   ----> cmp( S[pos], T[k]); ( 0 < k < j)
 (其中k值为T[0]...T[j-1]的字串中从首串和尾串的元素匹配个数 且 1=< k < j)

经过思考：上述3种操作已包含KMP模式匹配算法的所有基本操作;
 由于书上给出的要么是直接抽象的公式（不理解），要么讨论一般情况（乱用下表，也不知从

0还是1开始，就晕了）。所以，在此只能依次列举几个例子用归纳法总结规律了；

 （注：下面用 ~ 表示 因为， @ 表示 所以, |= 表示 有可能）；
eg1:
 当, j = 1；
 T = "a..."， S = "...x...";
  ~ a != x , @ 得操作 cmp( S[pos 1], T[0])
  即,当 j = 1时 nex[1] = -1;
eg2:
 当, j = 2;
 S = "...ax..." 
 1: T = "ab...";
  ~ b != x, b != a; @ a |= x;
  @ cmp( S[pos], T[0]) 即，nex[2] = 0;
 2: T = "bb...";
  ~ b2 != x, b2 = b1; @ b1 != x;
  @ cmp( S[pos 1], T[0]) 即，nex[2] = -1;
eg3:
 当, j = 3;
 S = "abx..,";
 1: T = "abc...";
  ~ c != x,  b != c,  a != c; @ b |= x,  a |= x;
  又 ~ b != a; @ cmp( S[pos], T[0])  即，nex[3] = 0;
 2: T = "aac...";
  ~ c != x,  a2 != c,  a1 != c; @ a2 |= x, a1 != x;
  又 ~ a2 = a1; @ cmp( S[pos], T[1])  即， nex[3] = k = 1;
 3: T = "cbc...";
  ~ c3 != x,  b != c3;  @ b |= x;
  又 ~ c1 != b; @ cmp( s[pos 1], T[0])  即，nex[3] = -1;
 4: T = "ccc...";
  ~ c3 != x; 又 ~ c1 = c2 = c3;
  @ c1 != x, c2 != x; @ cmp( S[pos 1], T[0]) 即， nex[3] = -1;
eg4:......

由上面的例子可以得出怎么样的规律呢？（没想到一个模式匹配算法也这么复杂，就为追求O(m n)的效

率，这不累死人嘛！）

  由以上例子可得出，求nex[j]的过程在于，当S[pos] = x != T[j] 时通过推断T[0]和T[j]的关系，

以及递推T[0]...T[j-1]子串间的关系可以得到nex[j]的值来进行相应的操作，这样避免了在普通模式

匹配中一些不必要的回溯；

     这些规律可以总结为：(此处为贴引用资料)
 （1）next[0]= -1  意义：任何串的第一个字符的模式值规定为-1。
 （2）next[j]= -1  意义：模式串T中下标为j的字符，如果与首字符
 相同，且j的前面的1—k个字符与开头的1—k
 个字符不等（或者相等但T[k]==T[j]）（1≤k 如：T=”abCabCad”则next[6]=-1，因T[3]=T[6]
 （3）next[j]=k   意义：模式串T中下标为j的字符，如果j的前面k个
 字符与开头的k个字符相等，且T[j] != T[k]（1≤k                      即T[0]T[1]T[2]。。。T[k-1]==
 T[j-k]T[j-k 1]T[j-k 2]…T[j-1]
 且T[j] != T[k].（1≤k (4) next[j]=0  意义：除（1）（2）（3）的其他情况。

(注：这几条这和我上面分析的对应关系:
 1：  eg1;
 2: (1)1-k相等部分： eg3: 3;
    (2)1-k不等部分:  eg2: 2,  eg3: 4;
 3:   eg3: 2;
 4:   eg2: 1,  eg3: 1;
)

{ 通过以上对照，便可轻松的分析出KMP的性质的本质：
 1：不用多做解释，x和T[0]不相等,必然 cmp( S[pos 1], T[0])
 2: 当T[0] = T[j] 且 x != T[j]时；
    (1):T[0] = T[j] 且 在在T[1]...T[j-1] 中不存在相等的子串，由此可知在T[0]...T[j-

1]中将不会出现自模式匹配，又因为T[0] = T[j] != x;
 所以，此时要进行的操作将会是 cmp( S[pos 1], T[0])
    (2):此时在T[0]...T[j-1]中会出现自模式匹配，
 但是，若此时移动k位到相应的模式串上后由于T[k]也就是自模式匹配串的下一个字符: T[k]

= T[j], 而T[j] != x, 所以，T[k] != x,所以还是不会匹配，由此可得：此时操作cmp(S[pos 1], T

[0]);
 3:此条和上面的第二条的第二条相似，只是由于T[k] != T[j],所以，由自匹配子串向后滑动k

位后T[k] |= x, 所以所得操作 cmp( S[pos], T[k]);
 4:其它的情况时，是除了上述情况，
     (1):除过情况一；
     (2):T[0]...T[j-1] 无相等子串 又 T[0] != T[j],则T[0] != x
得操作 cmp(S[pos], T[0]);
     (3):剩余2个情况归上述情况2(2)和3；
  由此可见情况4是上面三种情况的补集；
}

啊！到此我终于分析完了，好累啊！都熄灯了！

上面的4性质正好可以归结为说上的三句原话：
1)-1,当j = 0时;
2) Max{k | 0 <= k < j && str[0..k - 1] = str[j - k...j - 1]};
3)0,其他情况,此时匹配要从第一个位置重新开始.

开始时怎么也不理解，哈哈，现在理解了！看了半天6、7个小时没白看啊！明天就写出代码！