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

Question

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

例如:-

字符串 1 =rove

字符串 2=计算器

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

Answer 1

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

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

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

重复执行以下操作:检查是否 discrepancy == 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 万个字符。书中提到“Formosa”，因此“moors”的变位词作为 Moby Dick 的子串出现。但是，毫不奇怪，白鲸记中没有出现“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”的变位词。