用Java写一个kmp算法
时间: 2023-08-31 11:33:12 浏览: 94
### 回答1:
KMP算法是用来在一个文本串中查找一个模式串的算法,它的优势在于在找不到匹配的字符时,能够快速跳过不可能匹配的字符,从而提高查找效率。
下面是一个使用Java实现KMP算法的例子:
```
public class KMP {
// next数组表示模式串的前缀和后缀的最长公共部分的长度
private int[] next;
public KMP(String pattern) {
// 计算next数组
int len = pattern.length();
next = new int[len];
next[0] = -1;
int k = -1;
int j = 0;
while (j < len - 1) {
if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
}
// 在文本串text中查找模式串pattern
public int search(String text) {
int m = 0;
int i = 0;
int len = text.length();
int plen = pattern.length();
while (m + i < len) {
if (i == -1 || pattern.charAt(i) == text.charAt(m + i)) {
i++;
if (i == plen) {
return m;
}
} else {
m = m + i - next[i];
i = next[i];
}
}
return -1;
}
}
```
上面的代码中,我们首先通过构造函数计算出next数组,然后在search方法中使用KMP算法在文本串text中查找模式串pattern。 如果找到了匹配,search方法会返回匹配开始的位置,否则返回-1。
要使用KMP算法,你需要创建一个KMP对象,然后调
### 回答2:
KMP算法是一种字符串匹配算法,用于在一个主串中查找一个模式串的出现位置。下面是用Java语言实现KMP算法的示例代码:
```java
public class KMP {
public static int kmpSearch(String text, String pattern) {
int[] next = getNextArray(pattern);
int i = 0, j = 0;
while (i < text.length() && j < pattern.length()) {
if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == pattern.length()) {
return i - j;
} else {
return -1;
}
}
private static int[] getNextArray(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
public static void main(String[] args) {
String text = "ABCABBBBABCDABCDABCABD";
String pattern = "ABCDABCAB";
int pos = kmpSearch(text, pattern);
if (pos != -1) {
System.out.println("Pattern found at position " + pos);
} else {
System.out.println("Pattern not found");
}
}
}
```
在上述代码中,`kmpSearch`函数使用两个指针`i`和`j`分别在主串和模式串中遍历,根据`next`数组进行匹配操作。`getNextArray`函数计算了模式串的`next`数组,用于快速回退指针`j`。
以上是我用Java语言写的一个KMP算法的实现,通过运行主函数可以在指定的主串中查找指定的模式串,并返回第一次出现的位置。
### 回答3:
KMP算法是一种用来解决字符串匹配问题的算法,其核心思想是避免不必要的字符比较以提升匹配效率。下面是用Java实现KMP算法的示例代码:
```java
public class KMPAlgorithm {
// 构建next数组
private int[] buildNextArray(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
// KMP算法匹配字符串
public int kmpSearch(String text, String pattern) {
int[] next = buildNextArray(pattern);
int i = 0, j = 0;
while (i < text.length() && j < pattern.length()) {
if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == pattern.length()) {
return i - j;
} else {
return -1;
}
}
public static void main(String[] args) {
KMPAlgorithm kmp = new KMPAlgorithm();
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int index = kmp.kmpSearch(text, pattern);
if (index != -1) {
System.out.println("匹配成功,模式串位置在:" + index);
} else {
System.out.println("未找到匹配的模式串");
}
}
}
```
以上代码实现了KMP算法的主要逻辑。在构建next数组中,通过利用已经匹配成功的前缀和后缀的信息进行比较,得到next数组用于匹配时的优化。在主函数中,我们使用示例数据进行测试,输出匹配成功的位置。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![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)