用java语言实现KMP模式匹配算法,输出部分,提示部分用中文,并给出注释,完整源代码。,并给出详细的设计思想,并给出分析理论时间复杂度。
时间: 2023-06-27 13:06:01 浏览: 61
设计思想:
KMP算法是一种字符串匹配算法,可以在一个文本串S内查找一个模式串P的出现位置。它的时间复杂度为O(n+m),其中n为文本串S的长度,m为模式串P的长度。
具体实现思路如下:
1. 预处理模式串P,得到一个next数组,用于在匹配时判断匹配失败后模式串应该移动的位置。
2. 在文本串S中,从前往后匹配模式串P,如果匹配成功,则返回匹配位置,否则根据next数组移动模式串P,继续进行匹配。
详细设计及源代码如下:
```java
public class KMP {
// 计算next数组
public int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
int j = 0;
next[0] = 0; // 第一个字符的next值为0
for (int i = 1; i < pattern.length(); i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
// KMP匹配
public int kmp(String text, String pattern) {
int[] next = getNext(pattern);
int j = 0;
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == pattern.length()) {
return i - j + 1;
}
}
return -1;
}
// 测试
public static void main(String[] args) {
KMP kmp = new KMP();
String text = "BBC ABCDAB ABCDABCDABDE";
String pattern = "ABCDABD";
int pos = kmp.kmp(text, pattern);
if (pos == -1) {
System.out.println("未找到匹配的子串!");
} else {
System.out.println("匹配成功,子串位置为:" + pos);
}
}
}
```
时间复杂度分析:
在预处理模式串时,需要遍历模式串一次,时间复杂度为O(m);
在匹配时,需要遍历文本串一次,时间复杂度为O(n)。在匹配过程中,每次匹配失败时,都需要根据next数组移动模式串P,最坏情况下需要移动m位,因此移动次数不会超过n次。因此,总时间复杂度为O(n+m)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)