string - 每个滑动窗口位置的字典第一个固定大小的子字符串

Question

从给定的字符串中，我想在字符串中所有相同大小的子字符串中找到按字典排序顺序排在第一位的子字符串（一些固定大小的 k）。

我会在很长的字符串（大小 m）上滑动窗口来执行此操作，并且希望在我将它移动到字符串中时为每个滑动窗口（大小 n > k）位置找到该子字符串。

似乎微不足道的解决方案需要 m*O(n log(n)) 时间。

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

有更快的算法吗？

Answer 1

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

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