javakmp算法的实现
时间: 2023-11-09 19:56:34 浏览: 45
KMP算法的实现是通过计算模式串的next数组,然后在主串中进行匹配。在Java中,可以按照以下步骤实现KMP算法:
1. 首先,定义一个函数来计算模式串的next数组,即模式串T中每一个长度为j (0 < j < T.length) 的前缀所对应的next[j]的值。这个函数可以按照以下步骤进行计算:
- 初始化一个长度为T.length的next数组,并将其所有元素初始化为0。
- 使用两个指针i和j,分别指向模式串的第一个字符和第二个字符。
- 循环遍历模式串的字符:
- 如果T[i]等于T[j],则将next[j+1]的值设置为j+1,并将i和j都加1。
- 如果T[i]不等于T[j],则判断j的值:
- 如果j等于0,则将next[j+1]的值设置为0,并将i加1。
- 如果j不等于0,则将j更新为next[j]的值。
2. 定义一个函数来进行匹配,接收一个主串S和一个模式串T作为参数。这个函数可以按照以下步骤进行匹配:
- 使用两个指针i和j,分别指向主串和模式串的第一个字符。
- 循环遍历主串的字符:
- 如果S[i]等于T[j],则将i和j都加1。
- 如果S[i]不等于T[j],则判断j的值:
- 如果j等于0,则将i加1。
- 如果j不等于0,则将j更新为next[j]的值。
3. 在匹配过程中,如果j的值等于模式串的长度,则说明匹配成功,返回主串中匹配的起始位置。
下面是KMP算法的Java实现代码:
```java
public class KMP {
public int kmpMatch(String S, String T) {
char[] sArr = S.toCharArray();
char[] tArr = T.toCharArray();
int[] next = getNext(T);
int i = 0, j = 0;
while (i < sArr.length && j < tArr.length) {
if (sArr[i] == tArr[j]) {
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = next[j];
}
}
if (j == tArr.length) {
return i - j;
} else {
return -1;
}
}
private int[] getNext(String T) {
char[] tArr = T.toCharArray();
int[] next = new int[tArr.length];
int i = 0, j = -1;
next[0] = -1;
while (i < tArr.length - 1) {
if (j == -1 || tArr[i] == tArr[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
}
```