Python 如何提取两个字符串中的相同部分？

[blueboyggh]

要求相同部分在原字符串中是连续的，而且长度要达到 4 个字符：
举个例子：
A 字符串：我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。
B 字符串：今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。
然后从上面两个字符串中提取出“中了 500 万彩票”和“是个好日子”
除了每个字符串挨个字符遍历，还有其他好办法吗？主要是需要比对的字符串数量是几千这个数量级。

[cy18]

先 O(n^2)建个字典树，再做 n 次 O(n)的查询，总计 O(n^2)，不知道有没有其他更快或者更简单的办法。

[blueboyggh]

@cy18 虽然看不懂，但还是谢谢

[ladypxy]

这是要做关键词过滤/审核？

[xuanbg]

字符串转成字符的集合，取交集。

[cdwyd]

才几千个，循环完全扛得住。除非你对比的字符串长度不是你举例的长度

[cy18]

接收 O(n^3)的话，用 set 实现估计 10 行以内代码就能搞定。
搜了下有个现成的库 https://pygtrie.readthedocs.io/en/latest/，先把第一个字符串的按照起始位置生成 n 个字符串全塞到字典树里，再用对第二个字符串用 longest_prefix 函数做 n 次查询就搞定了。

[blueboyggh]

@cdwyd 确实不是举例的长度，字符串字数可能一百多字，甚至更多

[blueboyggh]

@ladypxy 没必要什么都往这上面想吧

[ClericPy]

使用 Python 提取两个字符串中长度超过 4 个字符的公共子串. 问了俩 gpt 类的答案都是遍历.
先抄答案实现一个试试, 性能不够再考虑 KMP 或者 trie 树优化, 还有那种带缓存的递归优化优化

[em70]

最长公共子序列（ Longest Common Subsequence ，简称 LCS ）是一种常见的字符串匹配问题，可以用动态规划来解决。下面是 Python 中求解最长公共子序列的示例代码：

```python
def longest_common_subsequence(str1, str2):
m = len(str1)
n = len(str2)

# 创建一个二维数组来存储最长公共子序列的长度
dp = [[0] * (n + 1) for _ in range(m + 1)]

# 填充 dp 数组
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# 从 dp 数组中恢复最长公共子序列
i, j = m, n
lcs = []
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
lcs.append(str1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1

return ''.join(reversed(lcs))

# 测试示例
str1 = "ABCBDAB"
str2 = "BDCAB"
result = longest_common_subsequence(str1, str2)
print("最长公共子序列:", result)
```

这段代码中，`longest_common_subsequence` 函数接受两个字符串 `str1` 和 `str2`，并返回它们的最长公共子序列。动态规划的核心思想是创建一个二维数组 `dp`，其中 `dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列的长度。然后，通过填充这个数组，最终可以从 `dp` 数组中找到最长公共子序列。

在示例中，最长公共子序列为 "BCAB"。

from chatgpt

[NoOneNoBody]

这个我写过好几个方案，基本没跳出两个思路
这两个思路都是定位一个尾字符向前或向后组 n 个字符，然后再匹配，跟 #6 所说是一样的
1. itertools.accumulate
2. 是 numpy 模拟 pandas.rolling
载入 pandas/numpy 很耗时，但如果项目本身就需要载入的话，用这个比较大量文字数据，倒是很好用
这个用的是向量函数，没什么优化空间，但数据量很大的话，反而有有优势

还有一个想法是 AC 自动机，主要是有些项目一早就预载了 AC 自动机的字典，匹配目标主要也是在字典范围内，没必要再去各个文字语句都拆解一遍，不过这个没有去做，因为这个暂时没有应用场景，前两个已经很快了

[Pipecraft]

OP 想要的是提取所有长度大于 4 的公共子序列，而上面一些回复说的是最长公共子序列，两个是不同问题。

如果只是执行一次的任务，那可以怎么简单怎么来。
比如，利用正则表达式可以 1 行代码解决。

```python
import re

str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"

result = re.compile(r'([^,.，。]{4,})(?=.*####.*?(?=\1))').findall(str1 + "####" + str2)

print(result)
# 输出: ['是个好日子', '中了 500 万彩票']
```

正则的贪婪匹配，比较契合 OP 这个的问题。

[blueboyggh]

@Pipecraft 十分感谢，再麻烦问一下，如果长度要求不是 4 ，而是 8 ，是不是只把正则代码里的 4 改成 8 就行了？

[flyqie]

要求相同部分在原字符串中是连续的，而且长度要达到 4 个字符

你这个提取结果是固定的吗，还是说根据句子动态调整？

[blueboyggh]

@flyqie 不太理解您的固定和动态调整的意思？

[flyqie]

@blueboyggh #15

不好意思看错了，请忽略该回复。

楼上老哥代码似乎已经解决了你的问题，4 改 8 的话#号数量也得改一下。

[blueboyggh]

@flyqie 我测试了一下，好像不用改#号数量也能用

[Pipecraft]

@blueboyggh #17 如果长度要求不是 4 ，而是 8 , `{4,}` 改成 `{8,}` 即可。
`####` 是分割两个字符串的，可以换成其他任意字符串。
`[^,.，。]` 可以把其他要排除的标点符号加进去，比如 !?; 等。
正则表达式里的 `?=\1` 改成 `?:\1` 可能性能会更好一点。

后来想了想，有些情况，提取的不完整。
比如
str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心，我也想中 500 万彩票。"
只提取了 '是个好日子', '中了 500 万彩票'。
‘ 500 万彩票’ 没有提取出来。
要完整的提取，str1, str2 换个位置，再执行一次，然后两个结果取并集就完整了。

```python
import re

pattern = re.compile(r'([^,.，。]{4,})(?=.*####.*?(?:\1))')

def find_common_subsequences(str1, str2):
result1 = pattern.findall(str1 + "####" + str2)
result2 = pattern.findall(str2 + "####" + str1)
return list(set(result1).union(set(result2)))

# TEST
str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心，我也想中 500 万彩票。"
result = find_common_subsequences(str1, str2)
print(result)

# 输出: ['是个好日子', ' 500 万彩票', '中了 500 万彩票']
```

[szdosar]

试试这个，运行结果是：['是个好日子，', '中了 500', '中了 500 万彩票', '中了 500 ', '是个好日', '中了 500 万', '中了 50', '是个好日子', '中了 5', '中了 500 万彩']
[Finished in 89ms]
```
def find_common_substrings(s1, s2, min_length=4):
# 创建一个二维数组，用于存储公共子串的长度
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
longest = 0
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
if dp[i][j] >= min_length:
common_substrings.add(s1[i - dp[i][j]:i])
else:
dp[i][j] = 0

return list(common_substrings)

# 示例
s1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"
s2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"
print(find_common_substrings(s1, s2))
```

[blueboyggh]

@Pipecraft 十分感谢您！祝您中 500 万！