给KnuthMorrisPrattStringMatcher类写个allmatches的方法,使其可以接受字符串文本并返回该字符串中出现模式的所有位置的 ArrayList
时间: 2024-02-09 12:12:31 浏览: 16
好的,以下是KnuthMorrisPrattStringMatcher类的实现,其中包含了allmatches方法:
```java
import java.util.ArrayList;
public class KnuthMorrisPrattStringMatcher {
private int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0;
int i = 1;
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;
}
public ArrayList<Integer> allmatches(String text, String pattern) {
ArrayList<Integer> matches = new ArrayList<>();
int[] lps = computeLPSArray(pattern);
int i = 0, j = 0;
while (i < text.length()) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == pattern.length()) {
matches.add(i - j);
j = lps[j - 1];
} else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return matches;
}
}
```
allmatches方法接受两个字符串参数,text和pattern,其中text是要搜索的字符串,pattern是要搜索的模式。它返回一个ArrayList,其中包含所有匹配模式的位置。具体实现是通过使用经典的Knuth-Morris-Pratt算法来实现的。