string - 寻找最小泛语法窗口的有效算法？

Question

A pangrammatic window 是包含所有 26 个字母的较大文本的子字符串。引用维基百科的一个例子，给定这段文字:

I sang, and thought I sang very well; but he just looked up into my face with a very quizzical expression, and said, 'How long have you been singing, Mademoiselle?'

文本中最小的全语法窗口是这个字符串:

g very well; but he just looked up into my face with a very quizzical ex

其中确实包含每个字母至少一次。

我的问题是:给定一个文本语料库，找到文本中最小全语法窗口的最有效算法是什么？

我对此进行了一些思考并提出了以下算法。我有一种强烈的感觉，这些都不是最佳的，但我想我会把它们作为起点发布。

有一个简单的朴素算法，运行时间 O(n²) 和空间 O(1):对于字符串中的每个位置，从该位置向前扫描并跟踪您要查找的字母我们已经看到了(也许在一个位向量中，因为只有 26 个不同的字母，所以占用空间 O(1))。一旦你找到了所有 26 个字母，你就有了从给定点开始的最短全语法窗口的长度。每次扫描可能需要时间 O(n)，并且有 O(n) 次扫描，总共 O(n²) 时间。

我们还可以使用改进的二分查找在时间 O(n log n) 和空间 O(n) 中解决这个问题。构建 26 个数组，一个对应字母表中的每个字母，然后将每个字母在输入文本中的位置按排序顺序填充到这些数组中。我们可以通过简单地扫描文本，将每个索引附加到与当前字符对应的数组来做到这一点。一旦我们有了这个，我们就可以在时间 O(log n) 中找到从某个索引开始的最短全语法窗口的长度，方法是在数组中运行 26 次二进制搜索以找到每个字符出现在输入数组中的最早时间或在给定索引之后。这些数字中最大的那个给出了字符串中最下方出现的“长杆”字符，从而给出了泛语法窗口的端点。运行此搜索步骤需要 O(log n) 时间，并且由于我们必须对字符串中的所有 n 个字符执行此操作，因此总运行时间为 O(n log n)，数组的内存使用量为 O(n)。

上述方法的进一步改进是将数组和二进制搜索替换为 van Emde Boas trees和前任搜索。这将创建时间增加到 O(n log log n)，但将每次搜索时间减少到 O(log log n) 时间，对于 O(n log log n) 的净运行时间和 O(n) 空间使用。

---

有没有更好的算法？

Answer 1

对于每封信，请跟踪最近的目击事件。每当您处理一个字母时，更新相应的瞄准索引并计算所有字母的瞄准索引的范围(最大-最小)。找到最小范围的位置。

复杂度 O(n)。 O(nlog(m)) 如果考虑字母大小 m。