请教查找子串问题

winchell

请教大佬，Python查找含错子串个数有没有好的方法啊，就是只要不匹配的字符少于n个都认为是子串，我现在只会从头逐个往后找，有没有高级一点的方式

qq1151985918

举个例子，听不懂

winchell

qq1151985918 发表于 2022-5-28 14:03
举个例子，听不懂

比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2个

qq1151985918

winchell 发表于 2022-5-28 15:09
比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2 ...

这个太笼统了，你要找不含错很简单，要找含错的十分困难。比如在一个长度10000的字符串找一个长度100含错20的字符串简直难如登天。

winchell

qq1151985918 发表于 2022-5-28 18:16
这个太笼统了，你要找不含错很简单，要找含错的十分困难。比如在一个长度10000的字符串找一个长度100含错 ...

额好吧，我现在的方法就是从头逐个过，比如先看比较第0到99个字符，然后比较第1到100个字符，倒是可以做出来，就是复杂度有点高了......

Twilight6

winchell 发表于 2022-5-29 10:37
额好吧，我现在的方法就是从头逐个过，比如先看比较第0到99个字符，然后比较第1到100个字符，倒是可以做 ...

滑动窗口算法了解下

wp231957

winchell 发表于 2022-5-28 15:09
比如字符串'12345578901234567890'，要查找子串'4567'的个数，不允许含错就是有1个，允许含一个错就是有2 ...

啥叫含错
那1234也是满足的，就是4个位置都错了而已

winchell

wp231957 发表于 2022-6-1 11:44
啥叫含错
那1234也是满足的，就是4个位置都错了而已

要求了最大含错数n的，n不同结果当然不同

winchell

不知道正则表达式能不能做到

qq1151985918

winchell 发表于 2022-6-7 20:50
不知道正则表达式能不能做到

看你一直没解决给你个简单代码吧，还是我跟你说的，如果字符串比较短容错值比较小可能还好，一旦数字很大是很庞大的计算量。没有你想的高级方式，只有穷举

1. def compare(s1, s2):
   
2.     """
   
3.     :param s1: str -> 字符串 s1
   
4.     :param s2: str -> 字符串 s2
   
5.         :: 应当 len(s1) == len(s2) > 0
   
6.     :return: int -> 返回 s1, s2 不同共几处
   
7.     """
   
8.    
   
9.     d = 0
   
10.     for x, y in zip(s1, s2):
    
11.         if x != y:
    
12.             d += 1
    
13.     return d
    
14. 
    
15. def find(s1, s2, n):
    
16.     """
    
17.     :param s1: str -> 字符串 s1 母串
    
18.     :param s2: str -> 字符串 s2 目标子串
    
19.     :param n: int -> 最大容错值
    
20.         :: 应当 len(s1) >= len(s2) >= n
    
21.     :return: list -> 返回所有符合条件的结果
    
22.     """
    
23.    
    
24.     subsets = [s1[i:i+len(s2)] for i in range(len(s1)-len(s2)+1)]
    
25.     res = [subset for subset in subsets if compare(subset, s2) <= n]
    
26.     return res
    
27.    
    
28. if __name__ == '__main__':
    
29.     s1 = '12345578901234567890'
    
30.     s2 = '4567'
    
31.     print(find(s1, s2, 0))
    
32.     print(find(s1, s2, 1))
    
33.    
    

复制代码