kmp算法的java实现
时间: 2023-10-12 19:19:49 浏览: 63
KMP算法是一种字符串匹配算法,用于在一个字符串中查找另一个字符串的出现位置。以下是KMP算法的Java实现:
```java
public class KMP {
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int index = kmp(text, pattern);
if (index != -1) {
System.out.println("Pattern found at index " + index + " in text");
} else {
System.out.println("Pattern not found in text");
}
}
public static int[] computeLPS(String pattern) {
int[] lps = new int[pattern.length()];
int i = 1;
int j = 0;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(j)) {
lps[i] = j + 1;
i++;
j++;
} else {
if (j != 0) {
j = lps[j - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
public static int kmp(String text, String pattern) {
int[] lps = computeLPS(pattern);
int i = 0;
int j = 0;
while (i < text.length() && j < pattern.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
if (j == pattern.length()) {
return i - j;
}
return -1;
}
}
```
在上面的代码中,computeLPS()方法计算模式字符串的最长前缀和后缀(longest proper prefix which is also suffix,简称LPS),kmp()方法使用该LPS数组来在文本字符串中查找模式字符串的出现位置。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)