java实现串的模式匹配
时间: 2023-12-02 22:54:45 浏览: 28
java中常用的串的模式匹配算法有暴力匹配算法、KMP算法、Boyer-Moore算法、Sunday算法等。
以下是KMP算法的java实现:
```java
public class KMP {
public static void main(String[] args) {
String text = "ababababc";
String pattern = "ababc";
int index = kmp(text, pattern);
if (index != -1) {
System.out.println("匹配成功,起始位置为:" + index);
} else {
System.out.println("未匹配成功");
}
}
/**
* KMP算法
* @param text 文本串
* @param pattern 模式串
* @return 匹配成功时返回起始位置,否则返回-1
*/
public static int kmp(String text, String pattern) {
int[] next = getNext(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;
}
}
/**
* 获取next数组
* @param pattern 模式串
* @return next数组
*/
public static int[] getNext(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;
}
}
```