每个滑动窗口位置的字典顺序第一个固定大小的子字符串
从给定的字符串中，我想找到字符串中所有相同大小的子字符串中按词典排序顺序排在第一位的子字符串（某个固定大小的 k）。
我会在很长的字符串（大小 m）上使用滑动窗口来执行此操作，并且希望在将其移动到字符串中时找到每个滑动窗口（大小 n > k）位置的子字符串。
看来这个简单的解决方案需要 m*O(n log(n)) 时间。
我想如果我在开始时进行正常排序，然后删除从最后一个窗口位置开头开始的子字符串并插入在当前窗口末尾结束的新子字符串，我可以得到 m*O(log(n))每次移动窗口时，窗口位置都会放入已排序的子字符串集合中。 （当然，我不单独存储子字符串，而只是保留它们在集合中的位置，因此空间需求只是 nk 个整数），
是否有更快的算法？
From given string, I want to find substring (some fixed size k) that comes first in lexiographical sort order among all substrings of same size in the string.
I would do this with sliding window over very long string (size m), and would like to find that substring for every sliding window (size n > k) position when I move it trough the string.
It seems that trivial solution would take m*O(n log(n)) time.
I think I could get to m*O(log(n)) if I make normal sort at the beginning and then just remove the substring that starts at the beginning of last window position and insert new substring that ends at the end of the current window position into already sorted collection of substrings every time I move the window. (of course I don't store substrings separetly but just keep their positions in the collection, so space requirement would be just n-k integers),
Is there faster algorithm for this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
令 m 为输入字符串的大小，n 为您要查找的字符串的长度。我认为你可以通过使用后缀树在 O(m) 时间内解决这个问题。
首先为输入字符串构建后缀树。这需要时间 O(m)。现在，在树上进行深度优先搜索，在每一步中始终选择字典顺序的第一个选择。在此过程中，您找到的第一个长度为 n 的字符串是按字典顺序排列的长度为 n 的第一个子字符串。对长度为 m 的字符串在后缀树上执行 DFS 需要时间 O(m)，因此总的来说，这需要时间 O(m)。
Let m be the size of the input string and n be the length of the string that you're looking for. I think you can solve this in time O(m) by using suffix trees.
Start by building a suffix tree for the input string. This takes time O(m). Now, do a depth-first search on the tree, always choosing the lexicographically first choice at each step. In the course of doing so, the first string of length n that you find is the lexicographically-first substring of length n. Doing a DFS over a suffix tree for a string of length m takes time O(m), so overall this takes time O(m).