DP+1 ,稍微调整一下 @
szdosar 的代码应该就可以改成同一序列取最长的了。时空复杂都是 O(M * N),滚动数组优化的话空间还可以做到 O(2 * min{M, N})。而且从比较次数来看应该比前缀树之类方法要更快。
```python
def find_common_substrings(s1, s2, min_length=4):
# 创建一个二维数组,用于存储公共子串的长度
s1 += '\0'
s2 += '\1'
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
common_substrings = set()
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
elif dp[i - 1][j - 1] >= min_length:
common_substrings.add(s1[i - dp[i - 1][j - 1] - 1:i - 1])
return list(common_substrings)
```