KMP
串匹配算法
效率真tm低不够还算搞明白了看在周末
份上原谅自己了呵呵
记录
下 命题:设计算法
在串s中从pos位置开始查找第个和目标串t相同子串起始位置 kmp算法实现:第
步预处理目标串t求出t中每个在和源串s中不等时移到位置思路方法是根据如下公式 next[0] = -1;
next[j] = max{k| 0<k<j && \"t0t1...t(k-1)\"
\"t(j-k)t(j-k+1)...t(j-1)\"}; next[j] = 0;
此公式可如下证明
首先
假设目标串下次移动到k位置那么这个k位置有什么特性呢k的前所有(k个从0开始)应该和源串s中i位置前k个相同即: \"t0t1...t(k－1)\"
\"s(i-k)s(i-k+1)...s(i-1)\" 而且
这时候源串i位置的前k个和目标串j位置的前k个也相同即: \"t(j-k)t(j-k+1)...t(j-1)\"
\"s(i-k)s(i-k+1)...s(i-1)\" 那么得到如下结论
\"t0t1...t(k－1)\"
\"t(j-k)t(j-k+1)...t(j-1)\" 第 2步
循环源串和目标串如下吧这段不好说了 while(s[i] != ’’ && t[j] != ’’)
{
(j -1 || s[i] t[j]) //j-1表示s[i]和t[0]区别 {
i
; j
; }
{
j = next[j];
}
}
(t[j] ’’) 
i-j; 0; 
最新评论