问题十
KMP模式匹配算法
问题描述：
判断模式串是否和待匹配串匹配
问题举例：
待匹配串：abababca
模式串：abc
返回：4
如果模式串不与待匹配串匹配则返回-1。
思路分析：
KMP模式匹配算法是一个非常经典的字符串匹配算法，要理解它主要是理解一个叫做next的数组，这个数组在各类算法讲解中都会出现，在此之前先理解一个叫做部分匹配表(Partial Match Table，PMT)的东西，简单来说这个表里面记录的东西就是字符串的前缀和后缀中重复字符串中最长的长度。
以abababca为例，
a前缀无，后缀无，pmt[0]=0
ab前缀a，后缀b，pmt[1]=0
aba前缀a、ab，后缀ba、a，重复的最长字符串为a，所以pmt[2]=1
abab前缀a、ab、aba，后缀bab、ab、b，重复最长为ab，所以pmt[3]=2
ababa前缀a、ab、aba、abab，后缀baba、aba、ba、a，重复最长为aba，所以pmt[4]=3
ababab前缀a、ab、aba、abab、ababa，后缀babab、abab、bab、ab、b，重复最长为abab，所以pmt[5]=4
abababc前缀a、ab、aba、abab、ababa、ababab，后缀bababc、ababc、babc、abc、bc、c，无重复字符串，所以pmt[6]=0
abababca前缀a、ab、aba、abab、ababa、ababab、abababc，后缀bababca、ababca、babca、abca、bca、ca、a。
综上所述
那么列出这个数组的意义何在呢，我们在abababca中查找ababca
可以看到当待匹配串在第i位、模式串在第j位失去匹配，此时按照传统暴力做法，就是将模式串ababca向右移一位。
然后重复进行判断，但是在KMP中就是充分利用已有资源，不回退模式串(暴力算法中算是已经匹配到了i位，但是失配之后却重新从第1位(以0为起始)开始重新匹配)，此时我们看到i前的那位，也就是第二个b处，其pmt值为2，这代表，其前缀前2位和后缀后2位是完全相同的，所以发生失配的时候，我们就知道了主字符串i之前的4位和模式串开头的4位相同的，则说明这部分不再需要比较了。那么如果要求next数组的话，就直接把PMT向右偏移，第0位设置为-1以方便编程的需求。
如果需要求next数组的值，则next[0]=-1，next[1]=0，因为这个next数组代表任一位置能匹配的最长长度的值，所以next[1]自然是0，这里的1代表的是第1位的数据，具体在abababca中就是a，由于它没有前后缀，所以为0。next[2]=0，ab的最大值为0。next[3]=1，aba公共部分长度为1…，以后的数组推导同理。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41public class KMP {
private int kmp(String ts,String ps){
int i = 0;
int j = 0;
int[] next = getNext(ts);
while (i<ts.length()&&j<ps.length()){
if (j==-1||ts.charAt(i)==ps.charAt(j)){
i++;
j++;
}
else
j = next[j];
}
if (j==ps.length())
return i-j;
else
return -1;
}
private int[] getNext(String ts){
int[] next = new int[ts.length()];
next[0] = -1;
int i=0,j=-1;
while (i< ts.length()-1){
if (j==-1||ts.charAt(i)==ts.charAt(j)){
++i;
++j;
next[i] = j;
}else
j = next[j];
}
return next;
}
public static void main(String[] args) {
KMP kmp = new KMP();
String s1 = "abababca";
String s2 = "bc";
System.out.println(kmp.kmp(s1,s2));
}
}
代码分析：
代码部分的重点主要是next数组的求法，这里求的next是待匹配字符串的next数组。默认next数组的next[0]是-1，然后就进行循环，if中的判断都比较直接，就是比较i和j位的字符是否相同，若相同就给next赋值，如同求解最长前后缀重复字符串一般。else中代表的就是失配的情况。
如同上图所示，第一行和第三行匹配时，前面的abab都是匹配的，但是当待匹配串匹配到c，模式串匹配到a时发生了失配，按照传统方法，由于发生失配，则模式串中的指针应该从第三个a处回退到第一个a处，从头开始重新匹配，但是在KMP中是找到next[j]的值，将它赋予j，这样就能给定j“指针”移动的大小，不需要再将之前肯定相等的字符串重新比较一遍。KMP主逻辑中的思想与getNext中的方法基本一致，可以按照以上思路进行分析。