/** * 获取指定字符串str从左到右依次 1生长的子字符串与前缀子字符串对应的中间子字符串长度形成的数组 * * @author yuni_xiumu 比如: getNext("asdfasdf3") = [0, 0, 0, 0, 0, 1, 2, 3, 4] * @param str * @return */ public static int[] getNext(String str) {
if (null == str || str.isEmpty()) return new int[0]; int[] next = new int[str.length()];// 自动默认填充0 int j = 0;// 用于储存与str中间子字符串的长度可以与前缀子字符串一对应 // 依次遍历str除一个元素(第一个和最后一个除外) for (int i = 1; i < str.length() - 1; i ) {
if (str.charAt(i) == str.charAt(j)) {
// 存在长度>=1中间子字符串可与前缀子字符串一对应 next[i 1] = j;// 记录匹配情况 i 1:表示str中下标:i 1左字符串中的匹配 } else {
j = 0;// 一旦中间子字符串与前缀子字符串不能一一对应，则放置0，继续判断剩余子字符串与前缀子字符串的匹配 // next[i 1] = 0;//因为Java默认情况下，该数组填充0，因此该步骤可以省略 } } return next; } /** * KMP算法实现了子字符串首次出现在父字符串中的位置 * * @param parentStr * @param subStr * @retrn */
public static int kmpSearch(String parentStr, String subStr) {
int[] next = getNext(subStr);
int parentStrIndex = 0;// 父字符串下标
int subStrIndex = 0;// 子字符串下标
while (parentStrIndex < parentStr.length()) {
if (parentStr.charAt(parentStrIndex) == subStr.charAt(subStrIndex)) {
subStrIndex++;
if (subStrIndex == subStr.length()) {
return parentStrIndex - subStr.length() + 1;
}
parentStrIndex++;
} else {
// 核心点:用于加快匹配速度
// 之前已经和子字符串匹配过了的可以适当跳过
parentStrIndex += subStr.length() - next[subStrIndex];
}
}
return -1;
}
public static void main(String args[]) {
System.out.println(Arrays.toString(getNext("asdfasdf3")));
String str1 = "ab-a--aba--aba";
String find = "aba";
System.out.println(kmpSearch(str1, find));
System.out.println("over");
}