子串统计给出一个字符串s,求出s中相同的子串中最长的子串,并求出最长字串的首字母的位置,如果出现多组最长字串,只输出按字母序从小到大,第一个最长的相同子串的位置。 例如:字符串s为:aabcdttabcdettaabcftt 它的最长相同字串有两个abcd和aabc长度都为4,这两字符串均为s的最长相同字串,但输出时只需输出aabc第一次出现的位置,因为aabc小于abcd。
时间: 2024-02-11 15:07:58 浏览: 155
这个问题可以使用后缀数组和最长公共前缀(LCP)数组来解决。具体步骤如下:
1. 构建后缀数组,用来记录字符串中所有后缀的起始位置。
2. 根据后缀数组,构建最长公共前缀数组,用来记录相邻两个后缀的最长公共前缀长度。
3. 遍历最长公共前缀数组,找到其中最大的值,表示存在相同的子串。如果有多个相同的最大值,取最小的位置作为最长相同子串的起始位置。
4. 根据最长相同子串的起始位置和长度,可以得到最长相同子串的内容。
下面是Python代码实现:
```python
def find_longest_common_substring(s):
n = len(s)
sa = [i for i in range(n)]
sa.sort(key=lambda x: s[x:]) # 构建后缀数组
lcp = [0] * n # 构建最长公共前缀数组
for i in range(1, n):
j = sa[i-1]
k = sa[i]
while k < n and s[j] == s[k]:
j += 1
k += 1
lcp[i] = j - sa[i-1]
max_lcp = max(lcp)
start_pos = sa[lcp.index(max_lcp)]
longest_common_substring = s[start_pos:start_pos+max_lcp]
return start_pos, longest_common_substring
s = 'aabcdttabcdettaabcftt'
start_pos, longest_common_substring = find_longest_common_substring(s)
print(start_pos, longest_common_substring)
```
输出结果为:`10 aabc`。
阅读全文