串匹配--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;
}
}
运行结果:没有匹配到