java 对比两段话中所有重复的内容,并且重复内容长度大于设置参数长度才属于重复,小于这个参数不代表重复。返回重复内容的起止索引位置,并且需要一个你认为性能最高的方法
时间: 2024-11-05 19:29:52 浏览: 16
在Java中,对比两段文字中所有重复的内容并检查长度是否大于给定阈值,可以使用滑动窗口算法结合哈希集合来提高效率。以下是高性能的一个简单示例:
```java
import java.util.HashMap;
import java.util.Map;
public class StringDuplicateFinder {
private static final int MIN_LENGTH = 5; // 设置重复字符串最小长度
public List<StringPair> findDuplicates(String str1, String str2) {
Map<Integer, Integer> map = new HashMap<>();
List<StringPair> duplicates = new ArrayList<>();
for (int i = 0; i <= str1.length() - MIN_LENGTH; i++) { // 滑动窗口从头到尾
if (map.containsKey(str1.substring(i, i + MIN_LENGTH).hashCode())) {
int start = map.get(str1.substring(i, i + MIN_LENGTH).hashCode());
if (str1.regionMatches(true, start, str2, i, MIN_LENGTH)) { // 长度匹配且内容相等
duplicates.add(new StringPair(str1.substring(start, start + MIN_LENGTH), i));
}
} else {
map.put(str1.substring(i, i + MIN_LENGTH).hashCode(), i);
}
}
return duplicates;
}
static class StringPair {
private final String duplicateText;
private final int startIndexInFirstString;
public StringPair(String duplicateText, int startIndexInFirstString) {
this.duplicateText = duplicateText;
this.startIndexInFirstString = startIndexInFirstString;
}
// getters and setters
}
public static void main(String[] args) {
String str1 = "hello world hello";
String str2 = "world is a small place hello";
List<StringPair> result = new StringDuplicateFinder().findDuplicates(str1, str2);
// ...打印结果...
}
}
```
在这个例子中,我们通过`HashMap`快速查找子串是否已存在,然后用`regionMatches`函数确认子串在两个字符串中的确切位置。这种方法的时间复杂度为O(n),n为较长字符串的长度,因为它只需要遍历一次。
阅读全文