以前学DS时没有搞懂KMP算法，后来KY又看了一遍，还是困惑，而如今静下心来啃了下，略感觉开了一点窍，书上的代码和算法思想看懂了，记录下来，以后备忘。。。
（1）
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖ ´
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 …pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 …pj-1 …pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 …pj-1 ¹ p1 p2 …pj (2)
则立刻可以断定
p0 p1 …pj-1 ¹ ts+1 ts+2 … ts+j
下一趟必不匹配
（2）
同样，若 p0 p1 …pj-2 ¹ p2 p3 …pj
则再下一趟也不匹配，因为有
p0 p1 …pj-2 ¹ ts+2 ts+3 … ts+j
直到对于某一个“k”值，使得
p0 p1 …pk+1 ¹ pj-k-1 pj-k …pj
且 p0 p1 …pk = pj-k pj-k+1 …pj
则 p0 p1 …pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
（3）
k 的确定方法
当比较到模式第 j 个字符失配时， k 的值与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理
如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf ( j-1)+1。
（4）
若设 模式 P = p0 p1…pm-2 pm-1
示例 ：确定失效函数 f (j)
int String::fastFind( String & pat ) const { int posP = 0, posT = 0; //两个串的扫描指针 int lengthP = pat.curLen, lengthT = curLen; //模式与目标串的长度 while ( posP < lengthP && posT < lengthT ) if ( pat.ch[posP] == ch[posT]) { posP++; posT++; } else { if (posP == 0) posT++; else posP = pat.f[posP -1] + 1; }
if(posP < lengthP ) return -1; //匹配失败，说明posT比较完了不够length，而posT还剩 else return posT - lengthP; //匹配成功
}
至于f[j]怎么计算，明天早上头脑清醒了再研究，O(∩_∩)O~
