Lexiographically每個滑動窗口位置

Question

從給定的字符串第一個固定大小的子，我想找到的子串（一些固定大小k）在首先出現在字符串中的相同尺寸的所有子之間lexiographical排序順序。

我會超過很長的字符串（大小M）滑動窗口做到這一點，並想找到各個滑動窗口子（大小n> k）的位置，當我移動它槽的字符串。

似乎微不足道的解決方案將會利用M * O（N日誌（n））的時間。

我想我可以得到m * O（log（n）），如果我在開始時進行正常排序，然後刪除從最後一個窗口位置開始的子字符串，並插入以子字符串結尾的子字符串每當我移動窗口時，將當前窗口位置的結尾放入已排序的子串集合中。 （當然我不存儲子separetly只是保持自己的位置集合中，所以空間要求是剛剛N-K整數），

對此有更快的算法？

Answer 1

設M是輸入字符串的大小，n是你要找的字符串的長度。我認爲你可以通過使用後綴樹來及時解決O（m）。

開始通過構建後綴樹輸入字符串。這需要時間O（m）。現在，在樹上進行深度優先搜索，在每一步中始終選擇字典順序的第一選擇。在這樣做的過程中，您找到的第一個長度爲n的字符串是長度爲n的字典順序第一個子字符串。對後綴樹做一個長度爲m的字符串的DFS需要花費時間O（m），所以總的來說這需要時間O（m）。