从给定的字符串中，我想找到在字符串中所有相同大小的子字符串中按字典排序顺序排在第一位的子字符串(某个固定大小的k)。
我将对非常长的字符串(大小为m)上的滑动窗口进行此操作，并且希望在通过字符串移动每个滑动窗口(大小为n> k)时找到该子字符串。
平凡解似乎需要m*O(n log(n))时间
我想我可以得到m*O(log(n))，如果我在开始时进行正常排序，然后删除从最后一个窗口位置开始的子字符串，并在当前窗口位置的末尾插入新的子字符串，每次我移动窗口时，它已经排序到子字符串的集合中。(当然，我不单独存储子字符串，而只是保留它们在集合中的位置，因此空间需求将只是n-k个整数)，
是否有更快的算法?
设m为输入字符串的大小，n为您要查找的字符串的长度。我认为你可以用后缀树在O(m)时间内解决这个问题。
首先为输入字符串构建一个后缀树。耗时O(m)现在，在树上执行深度优先搜索，在每一步始终选择按字典顺序排列的第一选择。在此过程中，您找到的长度为n的第一个字符串是字典顺序上长度为n的第一个子字符串。对长度为m的字符串在后缀树上执行DFS需要O(m)时间，因此总的来说需要O(m)时间。