public static void main(String[] args) {
String model = "aababcabcacbab";
String needle = "abcac";
int index = str(model, needle);
System.out.println(index);
}
public static int str(String model, String needle) {
int[] next = new int[needle.length()];
if (needle.length() == 0) {
return 0;
}
// 先计算出next函数对应值
for (int left = 0, right = 1; right < needle.length(); right++) {
// 不相等时left指针回退
while (left > 0 && needle.charAt(left) != needle.charAt(right)) {
left = next[left - 1];
}
if (needle.charAt(left) == needle.charAt(right)) {
left++;
}
next[right] = left;
}
// next数组装填完毕,进行字符串比对
for (int i = 0, j = 0; i < model.length(); i++) {
while (j > 0 && model.charAt(i) != needle.charAt(j)) {
// 当检测到不行等的字符时,就将模式串指针回退一个查找前一个的next[]对应的值,
// 数组中的值的含义是:在模式串中存在的最长匹配前缀和匹配后缀的长度是多少
// 因为在出现模式串和珠串字符不匹配时,可以确定模式串中,从不匹配的字符开始(但不包含),以前的串已经匹配完毕
// 最长匹配后缀与主串中对应字符串相等,也就表示最长匹配前缀与主串中的对应字符串相等,不用与主串再次匹配
// 如果回退过程中,在没有回退到原点时就可以匹配上那么就从此处开始继续匹配
j = next[j - 1];
}
if (model.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == needle.length()) {
// 返回字符串配配完成时对应的主串位置
return i - needle.length() + 1;
}
}
return -1;
}
学习连接:leetCode字符串匹配KMP算法详解



