小明接到一个破解报文的任务:该报文是一串文本,破解出的密文应是在报文串中出现次数大于1的所有子串中的最长者。规定报文本身不能称为自己的子串。请编写效率尽可能高的程序帮小明完成这个棘手的任务。
时间: 2023-06-05 13:47:17 浏览: 305
题目描述:小明接到一个破解报文的任务:该报文是一串文本,破解出的密文应是在报文串中出现次数大于1的所有子串中的最长者。规定报文本身不能称为自己的子串。请编写效率尽可能高的程序帮小明完成这个棘手的任务。
解题思路:首先,我们可以将所有长度大于1的子串都提取出来,并统计每个子串在原字符串中出现的次数。然后,我们可以遍历所有的子串,找出出现次数大于1的最长子串即可。
代码实现:
```python
def find_longest_substring(s):
n = len(s)
substrings = set()
for i in range(n):
for j in range(i+2, n+1):
substrings.add(s[i:j])
counts = {}
for substring in substrings:
count = s.count(substring)
if count > 1:
counts[substring] = count
longest_substring = ''
for substring, count in counts.items():
if len(substring) > len(longest_substring):
longest_substring = substring
return longest_substring
# 测试
s = 'ababcabcab'
print(find_longest_substring(s)) # 输出 'abcabc'
```
时间复杂度:$O(n^3)$,其中 $n$ 是字符串的长度。