是-K-子串與後綴樹

Question

我可怎麼辦下一步操作，用繩子S的後綴樹，誰的頂點數量爲O界函數（| S |）：

是-K - 子字符串（r） - 檢查字符串r是否爲s的k-子字符串，其中k-子字符串定義如下：

s的子字符串r定義爲k-字符串，如果有一個分區s到子字符串，其中：

r = x1x2 ... xk; xi = s的子串。例如：s = whitething，r = within，r是s的3個子字符串。

我需要該操作來處理O（| r |）的複雜性。

我不明白如何在O（| r |）上做到這一點，因爲r中的每個字符都可以是當前的分隔符，例如2-Sub-string，所以爲此我必須嘗試所有可能的字符作爲x1和x2之間的分隔符（對於分區r = x1x2）。

任何想法？

Answer 1

引理：如果A是B和B後綴可以拆分成S最多k子，這樣可以A。

證明：讓B = x[1] x[2] x[3] ... x[k]。讓我們扔掉分區的第一個|B| - |A|字符。我們將得到一個不超過k部分的分區。推論：如果我們有一個前綴爲R的固定分區，則存在一個最佳分區，其中下一個子字符串是我們可以採用的最長分區。

該解決方案緊接着來自上述證明。我們可以使各部分只要我們能：

pos = 0 
while pos < R.length: 
     take the longest prefix of R[pos:] that is a substring of R 
     move pos after the end of this substring 

該解決方案可在線性時間內實現的：我們只是從樹的根部開始，並保持只要他們去爲當前角色的轉變R。如果沒有，我們將當前部分添加到答案並從根重新開始。