KMP算法
一、普通的字符串匹配
平时我们在写普通的字符串匹配算法的时候，是拿着要匹配的串去匹配被匹配的串，字符逐个比较，当发现字符失配时，被匹配的字符串的指针要回到前一次开始匹配的指针的下一个位置。这里我们称要去匹配的字符串为模式串P，被匹配的字符串为主串S，即我们拿模式串P去匹配主串S，看看P是否是S的子串。
例如：主串S是“abcabdsfabcdfrt”，模式串P是“abcd”，开始匹配时，可以看到，S和P的字符串0、1、2位置的字符是相同的，到3位置时出现不匹配，这是根据我们以往的方法，我们将主串的指针回到刚开始匹配的位置的下一个位置，即回到主串的1位置，即字符b，再拿着模式串的0位置去匹配。以此类推，每次出现失配时，主串的指针都回溯到初始匹配位置的下一个位置，模式串的指针都回到模式串的0位置。
二、为何要用KMP算法
当我们的模式串P中，出现了连续相同的字符串时，例如P=“abcabx”，我们拿这个P和主串S=“abcabqqeeabcabxxxaxxaa”去匹配时。开始匹配可以看到，主串S的0、1、2、3、4位置和模式串的0、1、2、3、4位置的字符都是相同的，接着两个串的指针都下移，到了S的5位置的字符就和P的5位置的字符就出现吧不匹配，根据以往经验我们会将S的指针回溯到1位置接着和P的0位置进行匹配。这是我们发现，我们的P的0-1和3-4位置的字符串是一样的，而且S的0-4已经和P的0-4匹配是相同的，所以主串S的3、4位置和模式串P的0、1位置是相同的。
如果用主串的1、2位置与模式串从头匹配，则都是失配的，主串S的3、4位置和模式串P的0、1位置是相同的，所以我们就可以不回溯主串的指针，让模式串的2位置直接与主串的当前位置进行匹配即可。
三、KMP算法的数学推导
目前几乎所有将KMP算法的j都是从1开始的，为了让大家更好的理解，我在此证明阶段让j也从1开始计算。
根据上面的情况，我们推广到一般情况。我们用i表示指向主串的指针，j表示指向模式串的指针，当主串的第i个字符和模式串的第j个字符失配时，主串中的第i个字符（指针i不回溯）应该与模式串中的哪个位置的字符再比较呢，假设我们的主串已经和模式串匹配比较到模式串的第k个字符了，那么模式串的前k-1个字符一定和主串的第i-k+1到i-1个字符是相同的，即
P1 P2 ……Pk-1=Si-k+1 Si-K+2…… Si-1
而已经得到的部分匹配结果是
Pj-k+1 Pj-k+2 ……Pj-1=Si-k+1 Si-K+2…… Si-1
由以上两式推导得出
P1 P2 ……Pk-1= Pj-k+1 Pj-k+2 ……Pj-1
反之，若模式串中存在满足上式的两个子串，则当匹配过程中，主串中的第i个字符和模式串中的第j个字符比较不相等时，仅需要将模式串向右滑动至模式串中的第k个字符和主串中第i个字符对齐，（此时，由于模式串中前k-1个字符和第i-k到i-1位置的字符都是对应相同的，所以模式串中前k-1个字符的子串P1 P2 ……Pk-1必定与主串中第i个字符之前长度为k-1的子串Si-k+1 Si-K+2…… Si-1相等）接着匹配从模式串的第k个字符与主串的第i个字符比较起继续进行。
四、求每一个位置对应的k（即next数组）
我们用next数组来存取模式串中每一个位置对应的k值，即next[j]表示当模式串中第j个字符和模式串中相应的字符失配时，在模式串中重新和主串中该字符进行比较的字符的位置。
根据三中的数学推导，得到了next函数的定义（假设字符串起始位置是1）
当j=1时，next[j]=0;
当j!=1时，next[j]=max(k|1<k<j且P1 P2 ……Pk-1= Pj-k+1 Pj-k+2 ……Pj-1)此集合不 为空时。若此集合为空，next[j]=1。
例，求模式串“abaabcac”的next数组
|
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
模式串 |
a |
b |
a |
a |
b |
c |
a |
c |
|
Next[j] |
0 |
1 |
1 |
2 |
2 |
3 |
1 |
2 |
五、next数组的实现
已知第j项，求第j+1项
假设我们已经求得了next数组的前j项，当我们求第j+1项时。根据K（next[]）的定义，模式串P的前next[j]-1项和第j-next[j]+1到第j-1项是相同的，这时如果模式串P的第next[j]项和第j项相同，则next[j+1]=next[j]+1。
如果模式串P的第next[j]项和第j项不相同，我们为了减少模式串P前后字符的比较次数，我们接下来寻找下一个最长的已知的前后对应相等的字符串，而且这个字符串要以P的第j个字符结尾。
我们已知模式串的前next[next[j]]-1项等于其第next[j]- next[next[j]]+1到next[j]-1项，而且模式串P的前next[j]-1项和第j-next[j]+1到第j-1项是相同的，所以模式串的前next[next[j]]-1项等于其第j- next[next[j]]+1到第j项。这时，如果模式串的第next[next[j]项等于其第j+1项，next[j+1]=next[j]+1;否则以此往前迭代，如果全部不匹配，直到j=1，返回1，迭代结束。
求next数组的代码实现：
static void getNext(String str){
// 为方便操作,把字符串转换为字符数组;定义next数组;
char[] strKey = ("a"+str).toCharArray();
int[] next = new int[strKey.length];
// 初始条件,j从1开始.
int j = 1;
next[1] =0;
int k = next[j];
// 根据已知的前j位推测第j+1位
while (j < next.length - 1)
{
if (k == 0 || strKey[j] == strKey[k])
{
next[++j] = ++k;
}
else//不匹配时，往前寻找次长的子串
{
k = next[k];
}
}
//打印一下我们的next数组
System.out.print("next[]的值 ");
for (int i = 1; i < next.length; i++) {
System.out.print(next[i] +" ");
}
}
六、KMP算法整体代码实现
public class KMP {
/*
* Kmp函数实现寻找模式串str2在主串str1中的位置，返回值即为str2在str1中的位置，
* 如果str2不是str1的子串则返回-1.
*/
private static int Kmp(String str1,String str2){
//第一步 求next[j]数组
char[] strKey = str2.toCharArray();
int[] next = new int[strKey.length];
// 初始条件
int j1 = 0;
int k = -1;
next[0] =-1;
// 根据已知的前j位推测第j+1位
while (j1 < strKey.length - 1)
{
if (k == -1 || strKey[j1] == strKey[k])
{
next[++j1] = ++k;
}
else
{
k = next[k];
}
}
//打印一下我们的next数组
System.out.print("next[]的值 ");
for (int i = 0; i < next.length; i++) {
System.out.print(next[i]+1+" ");
}
System.out.println();
//第二步 根据求得的next数组进行字符串匹配
int j=0;//j指向模式串str2，i指向主串str1.
for (int i = 0; i < str1.length(); i++) {
if(j==str2.length()) return i-j;
if(str1.charAt(i)==str2.charAt(j)) j++;
else j=next[j]+1;
}
return -1;
}
//测试数据
public static void main(String[] args) {
String str1="12345abaabcac2356";
String str2="abaabcac";
int a=Kmp(str1,str2);
System.out.println(a);
}
}