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

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

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

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

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

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

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

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

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

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

最长公共子序列（ 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

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

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

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

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

```python
import re

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

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

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

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

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

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

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

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

@blueboyggh #15

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

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

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

@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 万彩票']
```

试试这个，运行结果是：['是个好日子，', '中了 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))
```

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

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

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

用 difflib.SequenceMatcher

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

不是 kmp 算法吗

@Pipecraft
@szdosar

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

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

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

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

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

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

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

你把要比较的内容放在两个文本文件中试试：
'''
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))
'''

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

方法有不是只有一套，对吧？
'''
#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))
'''

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

@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 结果

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

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

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

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

https://pastebin.com/raw/q3wf0h23

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

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

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

动态规划可以解决
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))

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

https://pastebin.com/raw/irdJS0iK


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

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

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

@szdosar
@NoOneNoBody

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

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

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

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

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

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

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

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

chatGPT 的回答

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)

@szdosar
@NoOneNoBody

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

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

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

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

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

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

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

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

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

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

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

@NoOneNoBody 期待新代码共享

@Pipecraft 使用 18#的代码后，测试 100 条数据时间从 63 秒变成 59 秒，好像变化不多，是不是我的问题？

@szdosar 感谢，测试使用新代码，结果里没有相互包含的子元素了

@blueboyggh #63
就此题来说，@szdosar #49 帖的代码足够好了，你是用这个测出最短时间的吧？
我现在只是翻翻 more_itertools 有没有可用的东西，如果没有，也就不会写出更高效率的了

https://stackoverflow.com/questions/66668405/python-sliding-windows-of-a-list
这里有个关于 moving window （移动窗口）的例子，感觉也差不多

@NoOneNoBody 好的，确实是#49 的时间最短，感谢

more_itertools 有个有趣的东西

more_itertools.substrings(iterable)

Yield all of the substrings of iterable.

>>> [''.join(s) for s in substrings('more')]
['m', 'o', 'r', 'e', 'mo', 'or', 're', 'mor', 'ore', 'more']

不过也是完全穷举，字符串越长应该效率越低

@blueboyggh #62 差不多会那样，毕竟相比匹配用的时间，compile 表达式的时间没有多少。

@blueboyggh #65
我这边测还是自己写的快

把
l = len(s)
前面重新加上
s = ''.join([x for x in s if x in ss])

这个看样子是不能省略的，因为这个逻辑是，原 s 所有和 ss 包含的字符连起来，过滤了不能匹配的字符
意味着最大匹配长度不会超过这个新字符串的长度，而且连续匹配的子串也一定在这个新的字符串内
这样会大幅度降低后面的循环次数 range(l - minlen + 1)

PS: 用这个分别过滤 s 和 ss 后，正则的方式就快了很多了……我这里测试反而正则变成最快的方法

@NoOneNoBody #68
秀逗了，长度 len 可以用这个，但匹配不能用这个，逻辑不对

abcdef vs abdf 结果是 ab
过滤后 abdf vs abdf 结果是 abdf
就不正确了

算了，今天到此为止，脑子都打结了，去娱乐一下

用 pygtrie 写了个，这库不支持部分前缀的查找，建树比较慢，查找比较快。优化下 trie 库内部的建树或者查找过程的话应该可以再快几个数量级。

import pygtrie

def build_tree(str1, min_len=4):
tree = pygtrie.CharTrie()
for begin in range(len(str1)):
for end in range(begin+min_len, len(str1)):
tree[str1[begin:end]] = (begin, end)
return tree

def find_prefixes(tree, str2, min_len=4):
result = set()
sub_len = 0 # Used to remove unnecessary substrings
for start in range(len(str2)):
longest_prefix = tree.longest_prefix(str2[start:])
if (longest_prefix.key is not None
and len(longest_prefix.key) >= min_len
and len(longest_prefix.key) > sub_len):
result.add(longest_prefix.key)
sub_len = len(longest_prefix.key)
sub_len -= 1
return result


str1 = "我今天特别开心啊，因为今天是个好日子，我中了 500 万彩票。"*10
str2 = "今天不是个好日子，因为邻居中了 500 万彩票，我今天不开心。"*10
tree = build_tree(str1)
result = find_prefixes(tree, str2)
print(result)

@Pipecraft
@NoOneNoBody

由于现在数据量上升到了将近 10w 条，现在跑完一遍数据需要二十多个小时，这个滑动窗口的方法，还有什么能优化的地方吗？比如上多线程啥的？

@blueboyggh #71
10w 条的话
1. 向量化函数
2. 一些机器学习方向的包，#70 那个不知道是不是，这种包都是需要花时间建模，然后应用很快
3. 多进程并发，多线程因为 GIL 没用

前两个需要学习成本，但学会就很有用，可以用到其他工作，不仅是字符串，尤其是大批量的数值计算
并发的话比较快上手，因为单例函数已经存在，建进程池而已，花点时间比较一下其他并发包的 performance ，有不少比原生更快的

@blueboyggh #71 可以保存跑过的数据的结果，下次不再计算这个部分，只计算增量的部分。

但是，如果每天都有新的 10 w 条数据，可以考虑多个机器同时跑然后汇总，毕竟都是可以独立运算的。