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

[blueboyggh]

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

[blueboyggh]

@szdosar 好的，我先用了楼上老哥的代码，先测试，回头再试试您的

[maocat]

这种需求以前我会安心写代码，现在我只想扔给 langchain

[ruanimal]

用 difflib.SequenceMatcher

[MoYi123]

1. 把 A 变成 suffix array, => O(A)
2. 遍历 B[idx :idx+4] ,找出所有的起始 index => O((4 * B) * log(A))
3 对 A 和 B 都算出 rabin-karp 数组 => O(A+B)
4. 遍历第二步得到的起始 index, 用二分算法 + 第三步的哈希, 确定结束位置 => O( B * log(B))

[qianckjuan]

不是 kmp 算法吗

[blueboyggh]

@Pipecraft
@szdosar

我发现用二位的代码，用我题目中的例子就可以正常运行，但是用我实际需要匹配的字符串，就找不到匹配项，可是明明里面就有匹配项。哪位能加个联系方式帮帮忙...有偿也可以

[szdosar]

你改一下 min_length=9 ，结果就是
['中了 500 万彩票', '中了 500 万彩']
[Finished in 133ms]
所以是不是这个的原因，长度问题？

[blueboyggh]

@szdosar 实际我的长度需求是 8 ，我改成 8 了，也不行，我题目中这个例子是可以的，但是我实际需要用的字符串不行

[blueboyggh]

@szdosar 我发现了，因为我是从 excel 表格里提取的内容，如果内容里有换行符，就会影响判断，即使换行符并不在需要提取的相同文本内，也不行，这是因为换行符会影响字符串提取吗？

[Pipecraft]

@blueboyggh #29 建议删除换行符以后，提取。
正则参数加上 multiline flag 可以匹配带换行符的字符串，
但是有换行符可能会匹配不到一些结果。

比如
str1="ABC\nD123"
str2="A\nBCD456"

这两个字符串去掉换行符，应该可以匹配 ‘ABCD’，如果不去掉换行符，就匹配不到了。

[szdosar]

你把要比较的内容放在两个文本文件中试试：
'''
def find_common_substrings(s1, s2, min_length=8):
# 创建一个二维数组，用于存储公共子串的长度
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)

# 添加一个函数来读取文件内容
def read_file_content(filename):
with open(filename, 'r', encoding='utf-8') as file:
return file.read()

# 使用上面的函数来读取 file1.txt 和 file2.txt 的内容
s1 = read_file_content('file1.txt')
s2 = read_file_content('file2.txt')

# 使用 find_common_substrings 函数来对比这两个文件的内容
print(find_common_substrings(s1, s2))
'''

[blueboyggh]

@szdosar 主要是我需要对比的数据是上千条的 excel ，一个一个复制到文本文档，效率太低了吧

[szdosar]

方法有不是只有一套，对吧？
'''
#find_common_substrings_excel
#读取 Excel 文件，使用 pandas 库。确保你已经安装了 pandas 和 xlrd 库。可以使用以下命令进行安装：pip install pandas xlrd openpyxl
import pandas as pd

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)

# 添加一个函数来读取 Excel 文件的内容
def read_excel_content(filename):
# 读取 Excel 文件的第一个工作表
df = pd.read_excel(filename, sheet_name=0)
# 获取第一列的内容并将其转换为字符串
return df.iloc[:, 0].astype(str).str.cat(sep=' ')

# 使用上面的函数来读取 Excel 文件的内容
s1 = read_excel_content('file1.xlsx')
s2 = read_excel_content('file2.xlsx')

# 使用 find_common_substrings 函数来对比这两个文件的内容
print(find_common_substrings(s1, s2))
'''

[blueboyggh]

@szdosar 感谢，目前正在测试之前的代码，跑了 3 个小时，跑了 1300 条数据了

[NoOneNoBody]

@Pipecraft
正则的表现让我有点失望，本以为正则比循环快，实测不是
不过你写的这个正则很精彩，我留下了，其他地方有用，先谢

@blueboyggh
下面两个是我之前写的，效率还可以

下面两个 if minlen>l: return [] 及相关可以省略，因为我的应用场景有词语，不少是“没必要比较”的，所以直接返回空。如果基本是长句，这个判断反而没必要
==================
def matchSubstrings(s:str, ss:str, minlen:int=2, reverse:bool=False):
'''
按出现先后顺序，寻找 s 中，与 ss 任意子串相同的子串\n
叠加的部分只选首个匹配，例如 638 vs 63/38 -> 只返回 63\n
minlen: int 最短匹配长度\n
reverse: bool->True 反向，寻找目标为 ss ，参考为 s
'''
if reverse: s, ss = ss, s
ac = itertools.accumulate
l = len(s)
if minlen>l: return []
lll, pos = 0, 0
for i in range(l - minlen + 1):
sss = [x for x in ac(s[i:])]
sss.reverse()
ll = len(sss)
for j,x in enumerate(sss[:ll - minlen + 1]):
if j>ll-lll and i<pos+lll: break
if x in ss:
lll = len(x)
pos = i
yield x
break
==================
缩进自行处理，基本是遇到冒号结尾的，后面的都向右缩进，没有向左回退的，大概能看懂
1. 说明中的“叠加”情况是比较麻烦的，如果需求不同，写法就不同了
2. 这个主要考虑“顺序”，是全匹配；匹配长度优先是另一种写法，需要 itertools.accumulate(s[::-1])类似，但思路有点区别，参照#6 ；长度优先可以适时 break 只返回“最长匹配”

下面这个是基于 numpy 和 pandas 的，因为是向量函数列操作，所以是全匹配，如果只需要“最长”的话，在某个 yield 后打 break ，或者要在返回结果中再筛选
===================
def rollingByNumpy(s:pd.Series, window):
v = np.lib.stride_tricks.as_strided(s, (len(s) - (window - 1), window), (s.values.strides * 2))
return pd.Series(v.tolist(), index=s.index[window - 1:])

def matchSubstrings4(s:str, ss:str, minlen:int=2, reverse:bool=False, whole:bool=True):
'''
按最大匹配长度的顺序，寻找 s 中，与 ss 任意子串相同的子串\n
叠加的部分默认只选首个匹配，例如 638 vs 63/38 -> 只返回 63 ； whole=False 时则全部返回，返回 63 和 38\n
minlen: int 最短匹配长度\n
reverse: bool->True 反向，寻找目标为 ss ，参考为 s\n

如果之前已经载入 pandas ，此函数略微快些，否则 载入 pandas 耗时较多
'''
if reverse: s, ss = ss, s
s1 = ''.join([x for x in ss if x in s])
l = len(s1)
if minlen>l: return []
s2 = pd.Series(list(s))

if whole:
for w in range(l, minlen-1, -1):
ser = rollingByNumpy(s2, w).str.join('')
ii = ser.index.min()
for i,x in ser.items():
if i<=ii+w: continue
if x in ss:
ii = i
yield x
else:
for w in range(l, minlen-1, -1):
ser = rollingByNumpy(s2, w).str.join('')
for x in ser:
if x in ss: yield x
==================
缩进自行处理，遇到冒号结尾的，后面的都向右缩进，基本没有向左回退的，大概能看懂
else 那行和 if whole 对应，没有缩进，其他都是向右缩进，回复没缩进会混乱

1. rollingByNumpy 因为用途很广，我好多地方用到，不仅是字符串，所以独立一个函数分开
pandas.rolling 不能用在整数、浮点以外的类型，所以需要用 numpy 模拟
rollingByNumpy 不是原创，是参考 so 的答案改的
2. 我原来的函数是重组一个 dataframe 返回的(也不需要 ss 参数)，因为后续根据需求不同（不一定是求子串），可以整个 dataframe 统一用一个函数(这里才使用到 ss)同时处理，没必要逐个处理；这里只是按 op 需求跑了一遍循环 yield 结果

[RuiCBai]

这不就是最长公共子数列嘛 （比最长公共子序列还简单一些）

[KAAAsS]

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)
```

[szdosar]

「 https://drive.google.com/file/d/1-Kv19SR2HITSiWnzs6XzI_JqyqcjpK2w/view?usp=sharing 」
- - - - - - - - - - - - - - -
感谢指点，我也就是半桶水，上面这个链接是源码。

[RedisMasterNode]

可以很暴力解决，如果数据量不太大

https://pastebin.com/raw/q3wf0h23

测试例子：
>>> str1 = "abcdefgandhahaok"
>>> str2 = "acsdefokokhhaha00"
>>> find_common_substrings(str1, str2, 3)
['def', 'hah', 'haha', 'aha']

[RedisMasterNode]

>>> find_common_substrings(str1, str2, 4)
['haha']