串匹配--KMP算法
next数组
首先我们先要了解一下什么是字符串的前缀和后缀
前缀
字符串的前缀是指字符串的任意首部。比如：望，望江，望江楼，望江楼上.......
后缀
字符串的任意尾部是字符串的后缀。比如：流，江流，江江流，望江江流......
前缀和后缀的公共子串
字符串前缀和后缀相同的字串。比如：“望江楼上望” 中的 字串“望”， “望江楼上望江”中的“望江”
图解求next数组
第一个字符前没有字符串，对应数组的值为-1（默认的）
第二个字符前的字符串，没有公共子串（从这里开始，next数组对应的值是.公共子串的长度）
第三个字符前的字符串，没有公共子串
第四个字符前的字符串，没有公共子串
第五个字符前的字符串，没有公共子串
第六个字符前的字符串，出现了公共子串“望”，长度是1，对应数组的值：1
第七个字符前的字符串，出现了公共子串“望江”，长度是2，对应数组的值：2
第八个字符前的字符串，没有公共子串
代码实现
public class KMP {
public static void main(String[] args) {
String s2 = "望江楼上望江江流";
int[] next = next(s2.toCharArray());
for (int i : next) {
System.out.print(i + ",");
}
}
public static int[] next(char[] str){
int k = -1; //记录公共子串的长度
int j = 0;
int strLength = str.length;
int[] next = new int[strLength];
next[0] = -1;
while (j < strLength-1){
if (k == -1 || str[k] == str[j]){
k++;
j++;
next[j] = k;
}else {
k = next[k];
}
}
return next;
}
}
运行结果：-1,0,0,0,0,1,2,0,
kmp算法
KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
图解
第一次匹配
第四个字符失配。字串的初始值为对应的第四个字符的next数组中的值 0。
第二次匹配
由于前三个是匹配的，而第四个字符失配，没有公共字串，那么无需再比较前三个字符。
这里的长串索引没有初始化，还是上次失配的值，就是3
短串初始值是0 
第三次匹配
第三个字符失配，短串初始值为对应的next数组中的0
第四次匹配
第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）
第五次匹配
第一个字符失配（就将长串索引+1，字串索引+1，代码中会有一个判断）
第六次匹配
第七个字符失配。出现了公共字串“望江”，下次字串的索引初始值是对应的2。
第七次匹配
长串的索引值还是上次失配的地方的值：14
短串初始值：2
后面的就省略了
........
代码
public class KMP {
public static void main(String[] args) {
String s1 = "望江楼，望江流，望江楼上望江流，江楼千古，江流千古";
String s2 = "望江楼上望江江流";
int result = kmp(s1, s2);
if (result == -1){
System.out.println("没有匹配到");
}else {
System.out.println("匹配到首次出现的索引位置是：" + result);
}
}
public static int kmp(String str1, String str2){
char[] longStr = str1.toCharArray();
char[] shortStr = str2.toCharArray();
int longStrLen = longStr.length; //长串的大小
int shortStrLen = shortStr.length; //短串的大小
int i = 0; //长串索引
int j = 0; //短串索引
while (i < longStrLen){
int[] next = next(shortStr);
if (j== -1 || longStr[i] == shortStr[j]){
i++;
j++;
}else {
j = next[j];
}
if (j == shortStrLen){
return i - j;
}
}
return -1;
}
public static int[] next(char[] str){
int k = -1; //统计公共字串的长度
int j = 0; //字符串的索引
int strLength = str.length;
int[] next = new int[strLength];
next[0] = -1;
while (j < strLength-1){
if (k == -1 || str[k] == str[j]){
k++;
j++;
next[j] = k;
}else {
k = next[k];
}
}
return next;
}
}
运行结果：没有匹配到
