场景:字符串匹配问题 1)有一个字符串 str1= “BBC ABCDAB ABCDABCDABDE”,和一个子串 str2=”ABCDABD” 2)现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1 3)要求:使用KMP算法完成判断,不能使用简单的暴力匹配算法. |
---|
1. 部分匹配值表
解析: A=1, 是因为从A开始,只有1个字符和前面重复;——》前后缀重复字符的长度
B=2, 是因为有连续2个字符所组成的字符串重复
package MeituanTest;
public class Main2 {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String subStr = "ABCDABD";
}
/**
* 写出KMP搜索算法
*
* @param str1 原字符串
* @param str2 字串
* @param next 字串的部分匹配表
* @return -1就是没有匹配到,否则就是第一个下标
*/
public static int kmpSearch(String str1, String str2, int[] next) {
// i: str1的下标, j: str2的下标
for (int i = 0, j = 0; i < str1.length(); i++) {
// 当二者不相等时
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i - j + 1;
}
}
}
// 获取字串的部分匹配值表
public static int[] kmpNext(String dest) {
// 因为需要拿到部分匹配值,所以要创建一个和字符串相同长度的数组
int[] next = new int[dest.length()];
// 在进行部分匹配值计算时,单个元素的字符串的字符永远对应值是0
next[0] = 0;
// 通用的情况,如果{abcdab},则第2次出现的a和b的匹配值都是1,第一次的a和b的匹配值仍为0
// 注意,这里的匹配是从头开始计算的,不是中间部分,比如: {1,2,3,a,4,5,6,a,7,8,9}, 从第2位开始遍历,每个元素都与首字符比较,不能跨过首字符
// 当有相同的字符时,长度j+1, 下标i也+1开始后续继续匹配
for (int i = 1, j = 0; i < dest.length(); i++) {
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1]; // 如果不想等,则代表局部匹配值表中,对应的相同sub字符串的长度不再+1
}
// i位和j位匹配,则部分匹配值+1
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
// 后面的字符的匹配值才会增加,前面的不会
next[i] = j;
}
return next;
}
}
KMP算法的核心: while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j - 1]; } |
---|