找到一組使用後綴數組兩個輸入串的重複的，不重疊的子串的

輸出：一組重複的，非重疊的子串

我必須找到的所有重複的字符串，每個字符串必須在兩個（！）字符串中至少出現一次。例如，讓

A =「xyabcxeeeyeyabczeee」和B =「yxabcxabee」。

然後一個有效的輸出是{「ABCX」，「AB」，「EE」}，而不是「EEE」，因爲它僅發生在串A.

我覺得這個問題是非常相關「超級重複」問題。下面是一個定義：

最大重複對：一對相同的子α和β的S中，使得在任一方向延伸的α和β 會破壞兩個串它表示爲一個的平等三重態（位置1，位置2，長度）

最大重複次數：「在S中出現在最大對中的S的子串」。例如：S = xabcyiiizabcqabcyrxar中的abc。注意：可以有多個最大重複對，但是最大重複數只能是有限的。

Supermaximal重複實施例「永不發生任何其它最大重複的子串的最大重複」：abcy在S = xabcyiiizabcqabcyrxar。

查找所有超最大重複的算法在「算法關於字符串，樹和序列」中描述，但僅限於後綴樹。

它的工作原理： 1）發現使用DFS

對於S，S中的每個位置i的所有左多樣節點第（i-1）被稱爲左字符I。 T（S）中葉的左字符是由該葉代表的後綴位置的左字符。如果v的子樹中的至少兩個葉子具有不同的左字符，則T（S）中的內部節點v被稱爲左多樣化。

2）這些節點上的應用定理7.12.4：

阿左多樣化內部節點v表示當且僅當所有的V的孩子都是葉子supermaximal重複一個，每個都有一個明顯的左字符

兩個字符串A和B可能已經被連接在一起，當我們查看v的葉子在第二步中，我們還必須施加額外的限制，即必須有字符串A和B中至少有一個不同的左字符。這可以通過將它們的位置與A的長度進行比較來完成。如果位置（左字符）>長度（A），則左字符在A中，否則在B中。

你能幫我解決後綴+ lcp數組這個問題嗎？

來源

2013-03-17 kafka

這聽起來像你正在尋找你的兩個輸入字符串的所有子串的集交集。在這種情況下，還應該返回單個字母的子字符串。讓s1和s2爲你的弦，s1爲兩者中較短的一個。做一些思考了一會大約在此之後，我不認爲你可以得到比直觀Ø更好的（N^3米）或爲O（n^3）的算法，其中n爲S1和米長度的長度的s2。我不認爲後綴樹可以幫助你。

for(int i=0 to n-1){ 
    for(int j=1 to n-i){ 
     if(contains(s2,substring(s1,i,j))) emit the substring 
    } 
}

運行時來自第（n^2）/ 2循環迭代，各做一個最壞情況下的O（nm）的包含操作（可能爲O（n），這取決於實現）。但它不是真的蠻這個壞，因爲會有一個常數遠小於一出來前，因爲串的長度將實際範圍1到n之間。
如果你不想單個字符匹配，你可以將j初始化爲2或更高。

BTW：不要實際創建新的字符串與字符串，找到/創建一個包含函數，將採取indicies和原始字符串，只是看看之間的字符，包容我的，獨家j的。

來源

2013-07-25 18:21:26

找到一組使用後綴數組兩個輸入串的重複的，不重疊的子串的

回答

相關問題