BF算法代码=strlen($t))$k=$i-strlen($t);否则$k=-1;返回$k;}$str1="abaabcabclkjlkff";$str2="abc";echobf($str1,$str2);?>复杂度最坏情况时间复杂度O(m*n)。m是模式字符串的长度。n是目标字符串的长度。KMP算法代码=strlen($t))$v=$i-strlen($t);否则$v=-1;return$v;}$s="ababcabcacbab";$t="abcac";$k;$k=KMPIndex($s,$t);echo$k;?>Timecomplexity时间复杂度为O(m+n).m是模式字符串的长度。n是目标字符串的长度。算法简单记忆分为两步：1.扫描模式串生成下一个数组，O(m)。2.主要字符串扫描，匹配，O(n)。KMP算法改进了BF算法的回溯问题，在整个匹配过程中只需要从头到尾扫描主串一次。其他php函数参数传递。定义函数时，在参数前加上'&'以通过引用传递。一般情况下都是按值传递，对象除外。PHP索引字符串中的字符。如果包含汉字，需要单独处理。js可以直接用“[]”来索引。Java使用charat函数。BM算法。考虑一个生成下一个数组的简单示例。考虑模式字符串t="abab"并观察下一个数组的生成过程。初始化。j=0k=-1next[0]=-1第一趟。j=1k=0next[1]=0第二遍。k=next[0]=-1第三次旅行。j=2k=0next[2]=0第四遍。匹配。j=3k=1next[3]=1第五趟。匹配。j=4k=2next[4]=2这里首先可以注意到第六步j=4，其实我们的模式串“abab”中的下标4已经越界了，嗯，不用担心，我们来看看每个循环都做了什么。如果($k==-1||$t[$j]==$t[$k]){$j++;$k++;$下一个[$j]=$k；}否则$k=$next[$k];代码只有5行，一个if...else...的判断语句。假设看过的同学已经在其他地方看到这里的前缀和后缀的原理了。如果k=-1或t[j]=t[k]，j++，k++，next[j]=k。这里的k=-1暂时不考虑它的作用，所以如果主串（模式串）匹配子串中的字符，主串的指针会往后退一位，子串的指针将返回一位，下一个数组将被赋值。否则k=next[k]。否则向前移动子串指针。这里也是根据下一个数组移动子串指针，需要抽象出子串的概念。所以，第六步匹配成功后，主串的子串移动，此后循环已经跳出。事实上，next[4]并没有用于目标字符串中的匹配。嗯。.记住要先尝试匹配，匹配成功则向后移动指针，不匹配则重置指针。这里k=-1可以理解为第一位不匹配时移动指针的条件。那你可以想想模式字符串“abcab”、“abcabd”、“ababab”等下一个数组的生成过程。理解kmp的关键是下一个数组是如何生成的。
