string - 字符串 2 的字谜是字符串 1 的子字符串

Question

如何找到字符串1的任意字谜词是字符串2的子字符串？

例如:-

字符串1 =漫游

字符串2=stackoverflow

因此它将返回 true，因为“rove”的字谜是“over”，它是字符串 2 的子字符串

Answer 1

编辑时:我的第一个答案在最坏的情况下是二次的。我已将其调整为严格线性:

这是一种基于滑动窗口概念的方法:创建一个由第一个字典的字母作为键控的字典，并包含相应值的字母的频率计数。将其视为需要与第二个字符串中的 m 个连续字母匹配的目标字典，其中 m 是第一个字符串的长度。

首先处理第二个字符串中的前 m 个字母。对于每个这样的字母，如果它作为目标字典中的键出现，则将相应的值减少 1。目标是将所有目标值驱动为 0。将差异定义为处理第一个 m 个字母窗口后的值的绝对值之和。

重复执行以下操作:检查是否存在差异 == 0，如果存在则返回 True。否则 -- 取 m 个字母前的字符并检查它是否是目标键，如果是 -- 将值增加 1。在这种情况下，这会将差异增加或减少 1，调整因此。然后获取第二个字符串的下一个字符并对其进行处理。检查它是否是字典中的键，如果是，则适当调整值和差异。

由于没有嵌套循环，并且每次通过主循环只涉及少量字典查找、比较、加法和减法，因此整体算法是线性的。

Python 3实现(展示了窗口如何滑动以及目标计数和差异调整的基本逻辑):

def subAnagram(s1,s2):
    m = len(s1)
    n = len(s2)
    if m > n: return false
    target = dict.fromkeys(s1,0)
    for c in s1: target[c] += 1

    #process initial window
    for i in range(m):
        c = s2[i]
        if c in target:
            target[c] -= 1
    discrepancy = sum(abs(target[c]) for c in target)

    #repeatedly check then slide:
    for i in range(m,n):
        if discrepancy == 0:
            return True
        else:
            #first process letter from m steps ago from s2
            c = s2[i-m]
            if c in target:
                target[c] += 1
                if target[c] > 0: #just made things worse
                    discrepancy +=1
                else:
                    discrepancy -=1
            #now process new letter:
            c = s2[i]
            if c in target:
                target[c] -= 1
                if target[c] < 0: #just made things worse
                    discrepancy += 1
                else:
                    discrepancy -=1
    #if you get to this stage:
    return discrepancy == 0

典型输出:

>>> subAnagram("rove", "stack overflow")
True
>>> subAnagram("rowe", "stack overflow")
False

为了对其进行压力测试，我下载了 Moby Dick 的完整文本。来自古腾堡计划。这有超过 100 万个字符。书中提到了“福尔摩沙”，因此“moors”的字谜词出现作为莫比迪克的子串。但是，毫不奇怪，《莫比迪克》中没有出现“stackoverflow”的字谜:

>>> f = open("moby dick.txt")
>>> md = f.read()
>>> f.close()
>>> len(md)
1235186
>>> subAnagram("moors",md)
True
>>> subAnagram("stackoverflow",md)
False

最后一次调用大约需要 1 秒来处理 Moby Dick 的完整文本，并验证其中没有出现“stackoverflow”的字谜。