//在控制台上输入一串字符串,输出字符串中最长重复的字符串如: //吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮”中最长重复的字符串为”葡萄皮" //abcdefgbcxyzdefg”中最长重复的字符串为defg
时间: 2024-01-08 15:03:06 浏览: 106
字符串中的最长重复串
要找出字符串中最长重复的子串,你可以使用以下的算法来实现:
1. 创建一个空的集合(Set),用于存储已经遍历过的子串。
2. 创建两个变量,分别用于记录当前最长重复子串的起始位置和长度。
3. 遍历字符串的每个字符,从第一个字符开始。
4. 对于每个字符,从当前位置开始向后查找,直到字符串的末尾。
5. 对于每个查找到的子串,如果它没有在集合中出现过,则将其添加到集合中。
6. 如果子串已经在集合中出现过,比较它的长度与当前最长重复子串的长度:
- 如果子串的长度大于当前最长重复子串的长度,则更新最长重复子串的起始位置和长度。
- 如果子串的长度等于当前最长重复子串的长度,则不进行更新。
- 如果子串的长度小于当前最长重复子串的长度,则不进行更新。
7. 遍历完所有字符后,根据最长重复子串的起始位置和长度,截取原始字符串中的最长重复子串并返回。
下面是一个示例代码实现(使用Java语言):
```java
import java.util.HashSet;
import java.util.Set;
public class LongestRepeatedSubstring {
public static String findLongestRepeatedSubstring(String str) {
int maxLength = 0;
int startIndex = 0;
Set<String> visitedSubstrings = new HashSet<>();
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
String substring = str.substring(i, j);
if (visitedSubstrings.contains(substring)) {
int length = j - i - 1;
if (length > maxLength) {
maxLength = length;
startIndex = i;
}
} else {
visitedSubstrings.add(substring);
}
}
}
return str.substring(startIndex, startIndex + maxLength);
}
public static void main(String[] args) {
String str1 = "吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮";
String str2 = "abcdefgbcxyzdefg";
System.out.println(findLongestRepeatedSubstring(str1)); // 输出:葡萄皮
System.out.println(findLongestRepeatedSubstring(str2)); // 输出:defg
}
}
```
运行这段代码,你将会得到与你提供的示例相同的结果。
阅读全文