在一个大字符串中查找多个单词，每个单词与另一个单词最多相距 k 个单词

Question

想象一下你收到了一长串

text

- 例如“敏捷的棕色狐狸跳过了懒狗和 lorem ipsum 等”，然后你会得到一个像

words

这样的

["quick", "brown"]

数组，以及一个 int

k

。如何编写一个

query

函数，它返回长字符串

start

中由

end

和

text

定义的范围，其中

text[start]

和

text[end]

都是

words

中和

 内的单词文本中start

和

end

，

words

中的所有单词都出现，最多相隔

k

个单词？

我希望对给定的长字符串

query

多次运行这个

text

函数，所以我希望有一个

O(f + s + t + ...)

的算法，其中

f

是

words中第一个单词出现的次数

text

中的

，

s

是

words

中第二个单词在

text

中出现的次数，依此类推。

我所拥有的是以下-

def query(text: str, words: list, k: int):
    word2idx_list = get_word2idx_list(text)

def get_word2idx_list(
    text: str,
):
    word2idx_list = defaultdict(list)
    words = text.split(" ")
    for i, word in enumerate(words):
        word2idx_list[word].append(i)
    return dict(word2idx_list)

但在此之后我陷入困境 - 我是否使用滑动窗口？

Answer 1

算法草图

• 输入：

  • k = 1

    # 单词之间的最大间隔

  • haystack = 'the quick ... lorem ipsum'.split()

  • needles = set('dog fox lazy'.split())

• 声明：

  • candidates = set()

    # 1 个或多个单词索引的元组

如果我们发现了一个元组，我们就赢了。

len(candidate) == len(needles)

。

第一个不变量：对于存储在每个候选中的每个索引

i

，情况将是

haystack[i] in needles

。

第二个不变量：扫描

sorted(candidate)

时，相邻索引之间的距离最多为

k

。

预处理

要让球滚动，请对干草堆进行线性扫描。在每个索引处我们

• 问是否

  haystack[i] in needles

• 如果是，插入几个1元组：

  • for j in range(i - k, i + k + 1):

    • candidates.add((j,))

筛选候选人

现在扩大这些候选人。

• 虽然候选长度小于

  len(needles)

  ：
  • 选择任意一个

    candidate

    ，将其从集合中删除

  • lo = min(candidate) - k

  • hi = max(candidate) + k

  • 做一个临时的

    ndls = needles.copy()

  • for i in candidate:

    • ndls.remove(haystack[i])

  • ndls

    是空的吗？哦，太好了，我们完成了！报告比赛。
  • 此时，

    ndls

    包含我们在

    lo

    ..

    hi

    范围内寻找的单词。

  • for i in range(lo, hi + 1):

    • if haystack[i] in ndls:

      • for j in range(i - k, i + k + 1):

        • candidates.add(candidate + (j,))

因此我们删除了一名候选人， 并可选择添加候选者以增加其长度。

挥手：我忽略了从干草堆的左侧/右侧逃跑。 添加 range() 帮助器，或者 考虑用

k

哨兵词填充两侧，这些词永远不会显示为针。

---

如果只需要第一场比赛，提前退出很容易。

要报告所有匹配项，请继续循环，直到候选集为空。 即使没有有效的匹配，它的大小也会变为零。

如果有H个大海捞针和N个针， 那么构建针组的成本为 O(N) O(H) 用于预处理扫描。 之后匹配率将占主导地位， 最坏情况下的成本为

O(k × N)

您可能会将其视为 

O(N)

。
这适用于主要由重复的针组副本组成的干草堆，但您不需要用于此类输入的奇特算法。
实际输入将看到运行时间与生成的候选数量成正比，这取决于 

k

 和匹配率。

---

替代算法

这是一个更简单的方法，不需要 遵循您概述的距离要求， 但可能适合您的需求。

• needles = { word: -math.inf for word in 'dog fox lazy'.split() }
• for i, word in enumerate(haystack):
  • if word in needles:
    • needles[word] = i
    • if min(needles.values()) >= i - k:
      报告比赛！

考虑对报告的匹配进行后处理 如果针之间的间隙过大会造成问题， 也许通过检查

sorted(needles.values())

 增量。

Answer 2

我的Python解决方案。 findMatch是所有滑动窗口发生的部分。 随意运行它，打印日志。

构建列表查询索引列表（def search的一部分）
将此列表列表[loL]传递给findMatch
occurrenceIdx 跟踪我们所在的查询词位置
occurrenceExhausted 跟踪确保我们仍然有所有查询词出现

import collections
def findMatch(loL, k):
    answer = []
    qlen = len(loL)
    occurenceIdx = collections.defaultdict(int)
    occurenceExhausted = False
    def _incrAllOccurences(occurenceIdx):
        for key in occurenceIdx:
            occurenceIdx[key] += 1
            if occurenceIdx[key] >= len(loL[key]):
                return True
        return False

    while (not occurenceExhausted):
        for idx in range(qlen):
            if idx == qlen-1:
                # for pdx in range(qlen):
                #     print ("->",pdx,":",loL[pdx][occurenceIdx[pdx]]," "),
                answer.append(loL[0][occurenceIdx[0]])
                occurenceExhausted = _incrAllOccurences(occurenceIdx)
                break
            if loL[idx + 1][occurenceIdx[idx + 1]] < loL[idx][occurenceIdx[idx]]:
                occurenceIdx[idx + 1] += 1
                if occurenceIdx[idx + 1] >= len(loL[idx + 1]):
                    occurenceExhausted = True
                break
            if loL[idx + 1][occurenceIdx[idx + 1]] - loL[idx][occurenceIdx[idx]] > k:
                occurenceIdx[idx] += 1
                if occurenceIdx[idx] >= len(loL[idx]):
                    occurenceExhausted = True
                break
    return answer
print ("findMatch " , findMatch([[1, 3, 8, 13, 23], [2, 4, 7, 14, 25],[5, 9, 16, 26] ], 2))
def search(text, query, k):
    wordDict = {}
    for idx, w in enumerate(text.split(" ")):
        if w not in wordDict:
            wordDict[w] = []
        wordDict[w].append(idx)
    queryWords = query.split(" ")
    listOfQueryIndices = []
    for qWord in queryWords:
        if qWord not in wordDict:
            return -1 #"inavlid query"
        listOfQueryIndices.append(wordDict[qWord])
    # pass list of list for sliding window
    return findMatch(listOfQueryIndices, k)

text = "The quick fox is quick"
query = "quick fox"
k = 1
print("search result", search(text,query,k))