每个滑动窗口位置的词法上第一个固定大小的子串

Question

从给定的字符串中，我希望在字符串中所有相同大小的子字符串中找到按词法排序顺序排在第一位的子字符串(某个固定大小的k)。

我会这样做的滑动窗口非常长的字符串(大小m)，并希望找到每个滑动窗口(大小n> k)位置的子串，当我移动它通过字符串。

平凡的解似乎需要m*O(n log(n))时间。

我想我可以得到m*O(log(n))，如果我在开始时进行普通排序，然后删除从最后一个窗口位置开始的子串，并在每次移动窗口时将结束于当前窗口位置的新子串插入到已经排序的子串集合中。(当然，我不会单独存储子字符串，而只是保留它们在集合中的位置，因此空间需求将仅为n-k个整数)，

有没有更快的算法呢？

Answer 1

设m是输入字符串的大小，n是要查找的字符串的长度。我认为你可以使用后缀树在O(m)时间内解决这个问题。

首先为输入字符串构建一个后缀树。这需要O(m)时间。现在，在树上进行深度优先搜索，始终在每一步中选择字典顺序上的第一个选择。在此过程中，您找到的第一个长度为n的字符串是按字典顺序排列的第一个长度为n的子串。对长度为m的字符串在后缀树上执行DFS需要O(m)时间，因此总体上这需要O(m)时间。