用Java编写kmp算法
时间: 2023-05-19 10:06:23 浏览: 84
KMP算法是一种字符串匹配算法,可以在一个文本串S内查找一个模式串P的出现位置。以下是用Java编写的KMP算法代码:
public class KMP {
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int index = kmp(text, pattern);
System.out.println("Pattern found at index: " + index);
}
public static int kmp(String text, String pattern) {
int[] lps = computeLPS(pattern);
int i = 0, j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
return i - j;
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1;
}
public static int[] computeLPS(String pattern) {
int[] lps = new int[pattern.length()];
int i = 1, len = 0;
lps[0] = 0;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}
希望这个代码能够帮到你!