用java语言实现KMP模式匹配算法,输出部分,提示部分用中文,并给出注释,完整源代码。
时间: 2023-06-27 08:07:07 浏览: 76
模式匹配之KMP算法(Java版)
以下是用Java实现KMP模式匹配算法的完整源代码:
```java
public class KMP {
// KMP算法实现
public static int kmp(String s, String p) {
int[] next = getNext(p);
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == p.length()) {
return i - j;
} else {
return -1;
}
}
// 获取next数组
public static int[] getNext(String p) {
int[] next = new int[p.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < p.length() - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
// 测试
public static void main(String[] args) {
String s = "ABC ABCDAB ABCDABCDABDE";
String p = "ABCDABD";
int index = kmp(s, p);
if (index == -1) {
System.out.println("未找到匹配子串");
} else {
System.out.println("匹配子串在主串中的位置:" + index);
}
}
}
```
代码中通过getNext()方法获取模式串p的next数组,并在kmp()方法中实现KMP算法。其中,i表示主串s中当前匹配的位置,j表示模式串p中当前匹配的位置。如果s[i] == p[j],则i和j都加1;如果不匹配,则j回退到next[j]的位置。如果最终j等于模式串p的长度,则表示匹配成功,返回i-j的位置作为匹配子串在主串中的位置;否则表示匹配失败,返回-1。
代码中还提供了一个简单的测试,用于验证KMP算法的正确性。
阅读全文