请教查找子串问题
请教大佬，Python查找含错子串个数有没有好的方法啊，就是只要不匹配的字符少于n个都认为是子串，我现在只会从头逐个往后找，有没有高级一点的方式{:10_266:} 举个例子，听不懂 qq1151985918 发表于 2022-5-28 14:03举个例子，听不懂
比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2个 winchell 发表于 2022-5-28 15:09
比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2 ...
这个太笼统了，你要找不含错很简单，要找含错的十分困难。比如在一个长度10000的字符串找一个长度100含错20的字符串简直难如登天。 qq1151985918 发表于 2022-5-28 18:16
这个太笼统了，你要找不含错很简单，要找含错的十分困难。比如在一个长度10000的字符串找一个长度100含错 ...
额好吧，我现在的方法就是从头逐个过，比如先看比较第0到99个字符，然后比较第1到100个字符，倒是可以做出来，就是复杂度有点高了...... winchell 发表于 2022-5-29 10:37
额好吧，我现在的方法就是从头逐个过，比如先看比较第0到99个字符，然后比较第1到100个字符，倒是可以做 ...
滑动窗口算法了解下
winchell 发表于 2022-5-28 15:09
比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2 ...
啥叫含错
那1234也是满足的，就是4个位置都错了而已 wp231957 发表于 2022-6-1 11:44
啥叫含错
那1234也是满足的，就是4个位置都错了而已
要求了最大含错数n的，n不同结果当然不同 不知道正则表达式能不能做到 本帖最后由 qq1151985918 于 2022-6-8 00:46 编辑
winchell 发表于 2022-6-7 20:50
不知道正则表达式能不能做到
看你一直没解决给你个简单代码吧，还是我跟你说的，如果字符串比较短容错值比较小可能还好，一旦数字很大是很庞大的计算量。没有你想的高级方式，只有穷举
def compare(s1, s2):
"""
:param s1: str -> 字符串 s1
:param s2: str -> 字符串 s2
:: 应当 len(s1) == len(s2) > 0
:return: int -> 返回 s1, s2 不同共几处
"""
d = 0
for x, y in zip(s1, s2):
if x != y:
d += 1
return d
def find(s1, s2, n):
"""
:param s1: str -> 字符串 s1 母串
:param s2: str -> 字符串 s2 目标子串
:param n: int -> 最大容错值
:: 应当 len(s1) >= len(s2) >= n
:return: list -> 返回所有符合条件的结果
"""
subsets = for i in range(len(s1)-len(s2)+1)]
res =
return res
if __name__ == '__main__':
s1 = '12345578901234567890'
s2 = '4567'
print(find(s1, s2, 0))
print(find(s1, s2, 1))
页:
[1]