【面向打野编程】——KMP算法入门

一、问题


  咱们先不管什么KMP,来看看怎么匹配两个字符串。

  问题:给定两个字符串,求第二个字符串是否包含于第一个字符串中。

  为了具体化,我们以 ABCAXABCABCABX 与 ABCABCABX为例。

正所谓:暴力出奇迹,枚举是真知。(大雾)先把代码敲出来再说,后面的事后面再考虑。

暴力/朴素匹配:时间复杂度O(N*M)

  虽然能够得到结果,但是速(bi)度(ge)太低。多看几遍就觉得这里出现了太多无用的计算,每次匹配失败就移动一格,实在挤牙膏。

  如果我们在每次匹配失败时多移动几位?

二、加速


KMP匹配:时间复杂度O(N+M)

  每次移动多一点,匹配速度快一点。在已经匹配过的字符串中,上面有部分的字符串与下面字符串的前面几个元素相同。

  利用已知字符,减少移动次数,比较未知字符,加快匹配速度。(KMP算法的思想)

  在每次的匹配中,已匹配的字符总是与下面字符串的前面部分(前缀)相同,又与上面字符串已匹配过的部分后面(后缀)相同。可以完全匹配的字符串都在下面的字符串中(废话)。

  因为只有每次匹配失败的时候才需要移动字符串,因此我们用一个fail/next/爱叫啥叫啥数组来记录移动的终点(下标)。

三、fail/next/爱叫啥叫啥数组


  开辟一个fail数组,fail[i]表示在匹配word[i]失败时,i需要跳转前往的下标。

  fail[i]也可表示word[0]~word[i-1]的最长公共前缀后缀长度。

  如果i跑到-1则表示:word字符串不想与你说话并把你踢出了队伍。

  来个循环,不断寻找自己的最长公共前缀后缀。由前面的匹配确定后面的fail数组的值,匹配失败直接使用fail数组(已确定的fail值)。

    "ABCA" 最长公共前缀后缀长度为1,即"A"。

    "ABCABC" 的最长公共前缀后缀长度为3,即"ABC"。

    ………………

 void setFail(){
int i = , j = -;
while (i < wLen){
if (j == - || word[i] == word[j]) fail[++i] = ++j;
else j = fail[j];
}
}

四、动手


匹配的时候,有问题,找fail,看题目,改条件。

 void setFail(){
int i = , j = -;
while (i < wLen){
if (j == - || word[i] == word[j]) fail[++i] = ++j;
else j = fail[j];
}
}
int fid(){
int i = , j = ;
while (i < tLen){
if (j == - || a[i] == word[j]) ++i, ++j;
else j = fail[j];
if (j == wLen){/*该做啥就做啥*/}
}
return -;
}

开始匹配

然后来一波入门题

POJ 3461/HDU 1686,HDU 2203,HDU 2594,HDU 1711


本渣才学疏浅,璞玉难琢,望各位神犇不吝赐(da)教(lian)。

上一篇:【PHP设计模式 10_ShiPeiQi.php】适配器模式


下一篇:Django Form和ModelForm组件