什么是KMP算法
Knuth-Morris-Pratt算法(简称KMP)是常用的字符串匹配算法之一。
假设现在有一个模式串a="ABACABAD"和一个主串b="BBC ABACABACABAD ABCDABDE"，要判断主串b是否包含模式串a，如果包含，则返回出模式串在主串的位置下标。
易知使用暴力匹配算法的时间复杂度为O(m*n),其中m和n为模式串和主串的长度。而使用KMP算法，则能在线性时间O(m+n)中完成匹配工作。
KMP算法实现逻辑
使用暴力匹配算法时，每次不匹配，都需要从主串下一个位置从头匹配一次模式串，这种回溯工作，导致效率低下。KMP算法核心思想是充分利用上次不匹配时的计算结果，避免"一切重新开始"的计算工作。
以下通过一个简单的例子进行说明：
1、首先，使用主串的第一位与模式串的第一位进行比较，如果不同，则将主串的第二位与模式串的第一位进行比较，以此类推。
比较主串第一位与模式串第一位的字符
比较主串第二位与模式串第一位的字符
2、直到主串有一个字符与模式串的第一位相同，则比较主串下一个位置的字符，是否与模式串的第二位相同，以此类推。
主串中的字符匹配到模式串的第一位字符
比较主串的下一个字符与模式串的第二位字符
3、当匹配到某个位置，主串与模式串的字符不同时，此时不直接从主串下一个位置，再从头逐个比较。因为在比较过程中，我们可以知道两个细节：
(1)模式串的前面部分的字符串内容是与主串的部分字符是相同的。
(2)在该模式串"ABACABAD"中，下标0~2的字符是与下标4~6的字符是相同的。
因此，我们直接使用下标位置为3的字符与主串进行比较，这样就能大大提高效率了。
主串字符C与模式串D不匹配
模式串下标0~2的字符是与下标4~6的字符相同，因此也与主串的前三个位置的字符是匹配的
不重头开始比较，而是比较模式串下标3的字符与主串中的字符是否相同
4、以此类推，直到匹配到模式串的最后一位，或者扫描完主串。
匹配到模式串的最后一位
部分匹配表
在匹配步骤3中，其实利用了模式串本身字符的组合顺序信息，在KMP算法中，我们需要将该字符组合顺序信息记录起来，称之为"部分匹配表"。
"部分匹配表"是如何产生的呢？首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符，一个字符串的全部头部组合,"后缀"指除了第一个字符，一个字符串的全部尾部组合。
例如字符串a="ABCAB"，前缀字符串集合为[A, AB, ABC,ABCA]，后缀字符串集合为[B, AB, CAB,BCAB]，可以看到前缀和后缀有相同的子串[AB]。
部分匹配值，其实就是计算出下标在0~i的子字符串中(i<=a.length)，前缀与后缀最长相同子串的长度。"部分匹配表"计算规则可参考阮一峰老师的日志“字符串匹配的KMP算法”。
我们根据这个规则，可计算模式串a="ABACABAD"的部分匹配表，如下：
KMP算法的JAVA 代码实现
1.计算部分匹配值。publicstaticint[]kmpnext(Stringdest){
int[]next=newint[dest.length()];
next[0]=0;
for(inti=1,j=0;i
while(j>0&&dest.charAt(j)!=dest.charAt(i)){
j=next[j-1];
}
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
next[i]=j;
}
returnnext;
}
代码说明：
1)声明部分匹配表数组，用于存储匹配值。
2)当字符串为空字符串str="",没有前后缀字符串，因此最长匹配值为0，next[0] = 0。
3)循环字符串，计算出下标在0~i的字符串的部分匹配表，i初始化为1。j用于记录前缀与后缀最长相同子串的长度。
(a) 如果在0~i的子字符串，j=0，并且dest.charAt(j) != dest.charAt(i)时，表示在0~i这一段中，前后缀字符串集合中没有相同字符串，因此next[i]=j(即next[i]=0)。
(b) 如果在0~i的子字符串，j=0，dest.charAt(j) == dest.charAt(i)时，表示在0~i这一段中，前后缀字符串集合中有一个字符串相同，因此j++;next[i]=j;(即next[i]=1)。
(c) 如果在0~i的子字符串，dest.charAt(j) ==
dest.charAt(i)时，如果j>0，则表示上一轮比较，在0~i-1的子字符串中，前缀与后缀有相同子串。因此在0~i这一段中，前缀与后缀也有相同子串，并且最长的共有字符串长度为j++。因此j++;next[i]=j。
(d) 如果在0~i的子字符串，j>0，dest.charAt(j) !=
dest.charAt(i)时，则表示上一轮比较时，字符串[0~j-1]是字符串[0~i-1]中，前后缀的最长相同字符串，如果我们找到在字符串[0~j-1]中的最长前后缀相同字符串(记作maxComStr)，继续比较maxComStr下一位与dest.charAt(i)，则能减少比较次数。通过部分匹配表中可见，next[j-1]为[0~j-1]中前后缀最长相同字符串的长度，我们也可以理解为是最长相同字符串下一个字符的下标，因此j=next[j-1]，举例说明：
dest.charAt(j) != dest.charAt(i)
字符串[0~j-1]中，前缀字符串集合为[A,AB]，后缀字符串集合为[A,BA],最长共有元素为A,j=next[j-1],则j移动到了该最长前缀字符串下一位
继续比较该最长前缀字符串下一位与dest.charAt(i)
2.比较模式串和主串。publicstaticintkmp(Stringstr,Stringdest){
//1.首先计算出部分匹配表
int[]next=kmpnext(dest);
//2.查找匹配位置
for(inti=0,j=0;i
while(j>0&&str.charAt(i)!=dest.charAt(j)){
j=next[j-1];
}
if(str.charAt(i)==dest.charAt(j)){
j++;
}
if(j==dest.length()){
returni-j+1;
}
}
return-1;
}
代码说明：
1)计算部分匹配表。
2)j为模式串a下标，i为主串b下标。循环主串，查找匹配位置。
(1) 如果j=0，并且str.charAt(i) != dest.charAt(j)时，则移动主串下标位置，比较主串下一位字符是否与模式串第一位字符相同。
(2) 如果str.charAt(i) == dest.charAt(j)时，则同时移动主串下标位置和模式串下标位置，依次比较下一位。
(3) 如果比较到模式串某个位置(j>0)，str.charAt(i) !=
dest.charAt(j)时，则根据部分匹配表，移动到[0~j-1]字符串的前后缀最长相同字符串的后一位，继续进行比较。如在该模式串dest
="ABACABAD"中，当j=7时，dest.charAt(7)与主串的字符不同。而dest[0~6]这部分字符串是与主串str[i-6~i-1]匹配的，dest[0~2]字符是与dest[4~6]的字符是相同的，由此可以推断出dest[0~2]的字符也与主串str[i-3~i-1]的字符是相同的。通过部分匹配表中可见，next[j-1]为前后缀最长相同字符串的长度，我们也可以理解为是最长相同字符串下一个字符的下标，因此j=next[j-1]。
(4) 当j == dest.length()时，表明完成模式串的比较，返回匹配起始位置(i-j+1)。
完整代码如下：publicclassKmp{
publicstaticvoidmain(String[]args){
Stringa="ABACABAD";
Stringb="BBCABACABACABADABCDABDE";
intresult=kmp(b,a);
//打印结果：和字符串获得匹配的位置System.out.println("resultPosion:"+result);
}
/***KMP匹配*/
publicstaticintkmp(Stringstr,Stringdest){
//1.首先计算出部分匹配表int[]next=kmpnext(dest);
System.out.println("next="+Arrays.toString(next));
//2.查找匹配位置for(inti=0,j=0;i
while(j>0&&str.charAt(i)!=dest.charAt(j)){
j=next[j-1];
}
if(str.charAt(i)==dest.charAt(j)){
j++;
}
if(j==dest.length()){
returni-j+1;
}
}
return-1;
}
/***计算部分匹配表*/
publicstaticint[]kmpnext(Stringdest){
int[]next=newint[dest.length()];
next[0]=0;
for(inti=1,j=0;i
while(j>0&&dest.charAt(j)!=dest.charAt(i)){
j=next[j-1];
}
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
next[i]=j;
}
returnnext;
}}
