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

[blueboyggh]

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

[RedisMasterNode]

补充一句刚刚测试了一下大约 2000 字符的对比，其实很快很快，主要看楼主希望达到什么程度，例如最差最差接受 1 秒执行完，那是非常轻松的，如果是真的有 1ms 内处理的需求再考虑其他方案就是了

[SaberJack]

动态规划可以解决
def longest_common_substring(s1, s2, min_length=4):
m = len(s1)
n = len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0
end_index = 0

for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_index = i
else:
dp[i][j] = 0

if max_length >= min_length:
return s1[end_index - max_length:end_index]
else:
return ""

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

print(longest_common_substring(A, B))

[22F41628gA98q4Lx]

两个字符串的公共子序列肯定包含楼主要的连续 4 个以上相同字符的序列。
其实只需要在状态表格中加多一个字段，表示已经有连续几个字符相同了。
以上算法的复杂度为 o(mn)
楼主可以先了解公共子序列的算法。

[blueboyggh]

https://pastebin.com/raw/irdJS0iK


@NoOneNoBody 麻烦给看看我处理的缩进和完善的 demo 是否有问题？测试结果只能输出一个“ 万彩票”

[liuhai233]

https://leetcode.cn/problems/longest-common-subsequence/

[szdosar]

我处理了一下你这个代码的缩进 https://pastebin.com/raw/6mEqdaZG
输出是：
'''
是个好日子，
[Finished in 131ms]
'''

[NoOneNoBody]

@blueboyggh #41
不对
1.交换 s/ss 那行缩进多了，但不影响
2.从 sss.reverse()开始到结束，都是在第一个 for 内部的，所以全部需要再增加缩进一层

[blueboyggh]

@szdosar
@NoOneNoBody

对，现在输出能出第一个相同字符串“是个好日子，”了，但是“中了 500 万彩票”没有，是因为我对 yield 返回的 x 的处理方式不对吗？

[szdosar]

不要执着于用迭代操作，我们来分析一下。
##itertools 是一个非常强大的库，它提供了很多用于处理迭代操作的工具。但是，对于特定的问题，直接的算法可能会更加高效。
##在我们的情境中，我们要找的是两个字符串之间的所有公共子串。使用 itertools 可能会涉及生成所有可能的子串组合，然后再进行比较，这在某些情况下可能会导致不必要的计算。
##而我们使用的滑动窗口方法是基于以下观察结果的：
##如果两个字符串在某个位置有一个公共字符，那么我们可以尝试扩展这个匹配，直到找到一个公共子串或匹配失败为止。
##通过这种方式，我们可以立即找到一个公共子串，而不需要生成和比较所有可能的子串组合。
##因此，对于这个特定的问题，滑动窗口方法可能会比使用 itertools 更加高效。但这并不意味着 itertools 不是一个有用的库。对于其他类型的问题，itertools 可能会提供更简洁、更高效的解决方案。
##以下使用滑动窗口方法
##find_common_substrings_huadong
源代码效率可大幅提高：
https://pastebin.com/raw/Qfr31L8a

[NoOneNoBody]

@blueboyggh #48
你是全部用了 #45 的代码吧？
他最后一句是用 next ，这个只返回第一个，改为 list(gg)是全部返回
如果想按长度排序（倒序），用 sorted(gg, key=len, reverse=True)

[blueboyggh]

@NoOneNoBody 谢谢，改成 list 就好了，next 是从网上抄的。

[NoOneNoBody]

@szdosar #49
滑动思路没有错，只是 window 的尺寸不定，从 min 到 length 都有，离不开每个 window 尺寸轮询
itertools.accumulate 在这里的作用就是自动生成不同 window 尺寸的切片，省了轮询的时间

如果尺寸固定，例如只找连续 4 个字符的匹配，5 个、6 个……都忽略，那用 pandas.series.shift 是对应最简单的思路
可惜 python 没有移动 window 概念，需要手写切片[start:end]

其实 @Pipecraft #12 写的利用正则贪婪匹配的思路是最精彩，虽然实际运行速度不如理想，但我还是忍不住要赞一个

我花了不少时间在这个上面，这个看上去是字符串问题，但实际是队列问题，如果能找到一个非常高效的方法的话，在 pandas 是非常有用的，大数据中快速寻找连续等值的片段用途多得很，所以我才写了个看上去跟字符串无不相干的 pandas 方案

[juny1998]

chatGPT 的回答

[juny1998]

def extract_common_substrings(str1, str2):
common_substrings = []

for i in range(len(str1)):
for j in range(i + 4, len(str1) + 1):
substring = str1[i:j]
if substring in str2 and len(substring) >= 4:
common_substrings.append(substring)

return common_substrings

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

common_substrings = extract_common_substrings(A, B)
print(common_substrings)

[blueboyggh]

@szdosar
@NoOneNoBody

我从我的样本里取了 100 条数据，用三种方法都进行了测试，测试结果：

滑动窗口方法：13 秒完成
itertools 方法：28 秒完成
正则表达式方法：63 秒完成

其中滑动窗口的方法，取出来的样本是最全的，但是结果 list 里一些子元素有相互包含的情况，比如“中了 500 万彩票”和“了 500 万彩票”
itertools 方法的结果更加精简，但是依旧有子元素有相互包含的情况
正则表达式方法则是完全没有子元素有相互包含的情况，但是速度也最慢

以上结果可能因为本人代码小白的问题受影响，不代表三种方法的真实水平，或者有其他隐含的坑我没能力发现

[szdosar]

可以改进的，返回的子串之间有相互包含的情况。我们在添加子串到结果集之前进行检查，可以检查新找到的子串是否包含在结果集中的任何子串中，或者结果集中的任何子串是否包含在新找到的子串中。
fix 源码 https://pastebin.com/raw/6aKqeUrP

[Pipecraft]

@NoOneNoBody #52 感谢对这个正则的肯定。
正则内部是通用的算法，肯定会比针对特定问题优化的算法速度慢。
所以上面（#12 ）回复里说了“如果只是执行一次的任务，那可以怎么简单怎么来。”
如果是反复执行并且数据量很大，那不建议用正则表达式。

#12 层里的代码并不完整，#18 层里的代码更完整，只是速度更慢。
https://pastebin.com/raw/UgzrPbA7

[Pipecraft]

@blueboyggh #55 处理多条数据时，正则表达式要使用 compile 后的结果，如果每次都 compile 一次，会很慢。
即不要直接使用 #12 层的代码，使用 #18 层的代码。
当然，我相信上面的测试是这么做的。

[blueboyggh]

@Pipecraft 我的问题，18#的源码我只应用了前后对比两次的逻辑，其他的没用，估计影响了结果，一会儿我修改一下再测试一下试试

[NoOneNoBody]

呵呵，发现自己有点钻牛角尖了，不追求 yield 和去叠加就没必要再轮询一次，可以少好多行代码

而且 itertools.accumulate 是先生成后比较，概率上无效的肯定更多，比起滑动跳过无效的，工作量更多
嗯，重练一遍