一、什么是KMP算法
首先说说什么是KMP算法，说白了，就是不希望用简单的两层循环遍历两个串那样去看能否匹配成功。简单朴素的字符串匹配是，一旦匹配不成功，主串要回到匹配开始的起始位置，然后加1再和模式串从头匹配。
二、 字符串匹配算法的实现思路（A暴力匹配和B通过next数组KMP算法实现）
主串：s='ababbabababbbab';
子串：p='abababbbab';
A ：暴力匹配实现。
·假设现在有这样一个问题：有一个文本串S，和一个模式串P，现在要判断S中是否有和P匹配的子串，并查找P在S中的位置，怎么解决呢？
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果匹配失败（即S[i]! = P[j]），令i = i - j + 1，j = 0，即每次匹配失败时，i 回溯到上次开始匹配的下一个位置，j 被置为0。
理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：
/** 2 * 暴力破解法 3 * 4 * @param ss 主串 5 * @param ps 模式串 6 * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1 7 */ 8 9 public int violentMatch(String ss, String ps) { 10 char[] s = ss.toCharArray(); 11 char[] p = ps.toCharArray(); 12 13 int i = 0; // 主串的位置 14 int j = 0; // 模式串的位置 15 while (i < s.length && j < p.length) { 16 if (s[i] == p[j]) { 17 //①如果当前字符匹配成功（即s[i]==p[j]），则i++，j++ 18 i++; 19 j++; 20 } else { 21 //②如果失败（即s[i]!=p[j]），令i=i-j+1，j=0 22 i = i - j + 1; 23 j = 0; 24 } 25 } 26 if (j == p.length) { 27 return i - j; 28 } else { 29 return -1; 30 } 31 }
暴力匹配算法，实现字符串匹配时间复杂度O(n+m)
B:KM算法实现。
1、next数组的概念
看过KMP的人都知道字符串前缀和后缀这两个概念，而我并不会说这两个概念。next数组通俗易懂的理解就是，对于模式串中每一个字符，看它前面字符串中存在的前缀和后缀匹配的最长长度。什意思呢？
二、next数组的求法
前面有对next求解的过程，然而那只是为了理解next的含义，真正算法编程却无法那样直观求出，那该如何求解next数组呢？这里用到了类似并查集的算法。
主串：abababbbab
- 首先next[0]=-1,next[1]=0；
- 之后每一位j的next求解:
比较j-1字符与next[j-1]是否相等，
如果相等则next[j]=next[j-1]+1,
如果不相等，则比较j-1字符与next[next[j-1]]是否相等，
1) 如果相等则next[next[j-1]]+1,
2)如果不相等则继续以此下去，直到next[…]=-1,则next[j]=0.
通俗易懂的话来说就是你要求解当前位的next值，则看前一位与前一位next所在位字符是否相等，相等则当前位的next等于前一位next+1，如果不等就找前一位next的next与前一位比较，如果相等，当前位的next等于那个与前一位字符相等的字符所在位置+1，如果还是不相等，则以此类推，直到出现比较位为next[]=-1，那当前位的next就等于-1。
然而在算法求解的时候，我们应该这样去理解，求解下一位的next等于当前位与当前位的next比较。
PHP代码实现：
<?php
function test(){
$str='ababxbababcadfdsssabcdabdrwgewwrabcdabd';
$p='abcdabd';
$next=array(0);
$t=KMP($str,$p,$next);
echo '---------------2222222222----------------';
print_r('---');
echo " \n";
echo $t ;
}
function getNext($p,$next){
$next[0]=-1;
$k=-1;
$j=0;
while($j<strlen($p)){
if($k==-1 || $p[$j] ==$p[$k] ){
$j++;
$k++;
$next[$j]=$k;
echo $next[$j];
}else{
$k=$next[$k];
}
}
return $next;
}
function KMP($str,$p,$next){
$next= GetNext($p,$next);
print_r($next);
$i=0;
$j=0;
$p_lenth=strlen($p);
$s_lenth=strlen($str);
echo 'str===='.$s_lenth;
while($i<$s_lenth && $j<$p_lenth){
if($j==-1 || $str[$i]==$p[$j]){
$i++;
echo'---iii==='.$i;
echo " \n";
$j++;
echo '----jjj====='.$j;
echo " \n";
}else{
$j=$next[$j];
}
}
echo 'i ==last=='.$i;
if($j==$p_lenth){
return $i-$j;
}
return -1;
}
test();
?>