请教查找子串问题

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
不知道正则表达式能不能做到

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

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 = [s1[i:i+len(s2)] for i in range(len(s1)-len(s2)+1)]
    res = [subset for subset in subsets if compare(subset, s2) <= n]
    return res
    
if __name__ == '__main__':
    s1 = '12345578901234567890'
    s2 = '4567'
    print(find(s1, s2, 0))
    print(find(s1, s2, 1))