找到給定單詞的雙子字的算法

Question

當它的形式爲u = ww時，給定單詞V的子字U是雙的，例如「abab」是「acdababx」的雙子字，但「cdab」不是。

我需要一個算法來檢查字V的給定子字U是否加倍。 V可以在線性時間進行預處理，但對於任何特定的U的回答應該具有恆定的時間複雜度，因爲對於每個V會有多個U.例如，如果V =「acdababx」，則給出U作爲間隔，區間[3 ..6]對應於子詞「大巴」。

例如輸入和輸出：

V = abbacbacca

U =

• [1 4] - >沒有
• [3 8] - >是
• [5 8] - >否
• [8 9] - >是
• [110] - > N

這不是任何當前比賽的問題。

Answer 1

這是一種算法，聲稱在輸入詞的後綴樹中標記所有雙字（或者在文獻中通常已知，串聯重複）的終點（其可以在O（n） ） 時間。當然，由於我沒有完全訪問該文章，我不確定它是否會滿足O（1）查詢時間。

論文是：Linear time algorithms for finding and representing all the tandem repeats in a string

希望有所幫助。