查找K最大的子串

Question

我給字符串S的長度爲10^5，現在所有可能的N+1C2子串我必須輸出K子串當所有子串按升序排序時。

For Ex: 
S= STACK 

Substring: 
    A 
    AC 
    ACK 
    C 
    CK 
    S 
    ST 
    STA ... so on 

My Approach：生成所有的子字符串進行排序和輸出K子串

後來我才知道Suffix陣列，對於一個給定的字符串我已經生成後綴數組，但如何計算K元素使用後綴數組？ 您能否解釋一下如何使用Suffix Array來計算K元素？

我已經生成並理解了後綴數組？但如何使用它。
Suffix Array Algorithm Used

Answer 1

後綴樹爲您提供了字符串的所有後綴。因此，如果字符串是「堆棧」，最長的後綴是堆棧$（我們添加一個虛擬的額外字符，以防止任何後綴成爲另一個後綴的前綴）。下一個最長的是大頭貼，然後確認$。所有這些都可以從根訪問。

現在子字符串只是後綴的前綴。通過走樹，你得到所有的子字符串，排序。這是一個相當昂貴的解決方案。 爲了讓搜索更便宜，假設我們想要K = 5。我們有一個後綴A並且它有三條到結尾符號$的路徑。所以A不是我們後綴的開始，我們沒有後綴B開始，所以這不是我們的答案。我們有一個後綴C開頭，它有兩個到$的路徑。所以對於k = 5，後綴的第一個字母必須是'C'。然後我們擴展。我們失去了三個位置，所以我們需要第一個C節點下的第二個後綴。