BF算法

代码

    = strlen($t)) $k = $i - strlen($t);    else $k = -1;    return $k;    }$str1 = "abaabcabclkjlkff";$str2 = "abc";echo bf($str1,$str2);?>

复杂度

最坏情况的时间复杂度O(m*n)。m为模式串长度。n为目标串长度。

KMP算法

代码

    =strlen($t)) $v = $i - strlen($t);    else $v = -1;    return $v;}$s="ababcabcacbab";$t="abcac";$k;$k = KMPIndex($s,$t);echo $k;?>

时间复杂度

时间复杂度为O(m+n)。m为模式串长度。n为目标串长度。

算法简单记忆分为两步:1.模式串扫描，生成next数组，O(m)。2.主串扫描，匹配，O(n)。KMP算法对BF算法的回溯问题进行了改进，在整个匹配过程中对主串仅需从头至尾扫描一遍。

其他

1. php函数参数传递。在定义函数时在参数前加上'&'改为引传递。一般情况为值传递，对象除外。

2. php在字符串索引某个字符。若包含中文字符需要另行处理。js可以通过"[]"直接索引。java用charat函数。

3. BM算法。

思考

看一个生成next数组的简单例子。

考虑模式串t="abab",观察一下next数组的生成过程。

1. 初始化。j=0 k=-1 next[0]=-1

2. 第一趟。j=1 k=0 next[1]=0

3. 第二趟。k=next[0]=-1

4. 第三趟。j=2 k=0 next[2]=0

5. 第四趟。匹配。j=3 k=1 next[3]=1

6. 第五趟。匹配。j=4 k=2 next[4]=2

这里首先可以注意到在第六步中j=4，而实际在我们的模式串"abab"中4这个下标已经越界了，嗯嗯，不要着急，我们先来看看在每一趟循环中到底做了什么。

if($k==-1||$t[$j] == $t[$k]){            $j++;            $k++;            $next[$j]=$k;        }        else $k = $next[$k];

代码不过5行，一个if...else...的判断语句。假设看的同学已经在其他地方看过这里前后缀的原理了。

如果k=-1或t[j]=t[k],j++,k++,next[j]=k。这里的k=-1暂时不考虑他的作用，那么就是如果主串（模式串）与子串中的字符匹配，则主串指针向后一位，子串指针向后一位，给next数组赋值。否则k=next[k]。否则向前移动子串指针。这里也是根据next数组移动子串指针并且需要注意抽象出子串的概念。

所以在第六步中匹配成功以后主串子串移动，在这之后已经跳出循环了。而实际上next[4]在目标串中匹配是用不到的。

嗯。。要记住是先尝试匹配，成功后在向后移动指针，不匹配则重置指针。

这里的k=-1可以理解为当首位不匹配时移动指针的一个条件。

紧接着可以思考模式串"abcab"，"abcabd"，"ababab"等next数组的生成过程。理解kmp的重点在于next数组是如何生成的。