KMP算法 的原理和java实现例子
时间: 2023-06-04 18:04:56 浏览: 83
KMP算法是一种字符串匹配算法,通过预处理模式串的最长公共前后缀,实现在匹配过程中跳过一定的比较步骤,从而提高算法效率。其Java实现例子如下:
public class KMP {
public static void main(String[] args) {
String pat = "ABCDABD";
String txt = "ABC ABCDAB ABCDABCDABDE";
int[] next = getNext(pat);
int index = search(txt, pat, next);
System.out.println(index);
}
public static int[] getNext(String pat) {
int[] next = new int[pat.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < pat.length() - 1) {
if (j == -1 || pat.charAt(i) == pat.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
public static int search(String txt, String pat, int[] next) {
int i = 0, j = 0;
while (i < txt.length() && j < pat.length()) {
if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == pat.length()) {
return i - j;
} else {
return -1;
}
}
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)