KMP模式匹配算法 Java实现

在字符串操作中，子串定位操作通常被称为串的模式匹配，即在主串中找子串是否存在;
若存在需要能定位到字串首次出现的位置。

朴素的模式匹配算法

public class KMP {
public int naiveStringMatch(String S, String T) {
char[] s = S.toCharArray();
char[] t = T.toCharArray();
int n = s.length;
int m = t.length;
int i = 0;
int j = 0;
while (i < n && j < m) {
if (s[i] == t[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == m) return i - m;
return -1;
}
public static void main(String[] args) {
System.out.println(new KMP().naiveStringMatch("abcgoogle","google"));
}
}

朴素的KMP模式匹配算法

KMP 算法的思想主要是在字符串匹配的过程过避免没有必要的回溯发生。

朴素KMP算法 保持 i 值不变，将 j 值设为合适的值 即可避免大量不必要的回溯
对于 j 值的变化储存在 next[j] 数组 中
当数组默认均以 0 为起始下标，next[] 为

next[i]=⎧⎩⎨⎪⎪−1,Max{k|1<k<i，且′p1...pk−1′=′pi−k−1...pi−1′},0,当 i = 0此集合不为空时其他情况 n e x t [ i ] = { − 1 , 当  i  = 0 M a x { k | 1 < k < i ， 且 ′ p 1 . . . p k − 1 ′ = ′ p i − k − 1 . . . p i − 1 ′ } , 此集合不为空时 0 , 其他情况

第二条指的是，前 i 个字符中，如果前缀字符串和后缀字符串匹配， next[i] = 前缀字符串最后一个下标的下一个
如 abcad ，计算 next[4] 的时候， i = 4 个字符 abca 中除前后两个 a 相等外无其他前后相等，
这时候 next[4] = a 的后一个元素 b 的下标 = 1

例子：google 的 next[] 为 [-1, 0, 0, 0, 1, 0, 0]

public class KMP {
// 生成 next 数组
public int[] genNextArray(String T) {
char[] t = T.toCharArray();
int[] next = new int[t.length];
int i = 0;
/* T[i] 表示后缀的单个字符 */
int j = -1;
/* T[j] 表示前缀的单个字符 */
next[0] = 0;
while (i < t.length - 1) {
if (j == -1 || t[i] == t[j]) {
i++;
j++;
next[i] = j + 1;
} else {
j = next[j] - 1;
}
}
for (int k = 0; k < next.length; k++) {
next[k] -= 1;
}
return next;
}
// kmp 匹配
public int kmpStringMatch(String S, String T) {
char[] s = S.toCharArray();
char[] t = T.toCharArray();
int n = s.length;
int m = t.length;
int i = 0;
int j = 0;
int[] next = genNextArray(T);
while (i < n && j < m) {
if (j == -1 || s[i] == t[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == m) return i - m;
return -1;
}
public static void main(String[] args) {
KMP kmp = new KMP();
System.out.println(kmp.kmpStringMatch("abcgloogle","gle"));
}
}

改进的模式匹配算法 (待续)

最后

以上就是贪玩小甜瓜为你收集整理的KMP模式匹配算法 Java实现的全部内容，希望文章能够帮你解决KMP模式匹配算法 Java实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。