在數組中查找所有重複的子序列

我不擅長算法設計，但在面試中遇到了這個問題。我的解決方案很幼稚，複雜程度很高，但可以在更短的時間內完成。在數組中查找所有重複的子序列

給定一個整數數組，找出該數組在數組中重複的所有子序列。打印子序列，然後開始索引和結束索引的所有發生。

e.g 1,0,1,9,5,1,9,5,1

這應該打印

1,9,5 

3:5 6:8 

9,5,1 

4:6 7:9 

1,9 

3:4 6:7 

5,1 

5:6 8:9 

9,5 

4:5 7:8

我的解決辦法是從Arr[0]開始至Arr[N/2 -1]和1檢查，如果它重複那麼就減少了最終指數繼續檢查，如果它重複。

感謝

2015-06-15 anonymous

你在談論連續或不連續的子序列嗎？他們是否應該彼此相鄰？您的樣本數組中重複了幾次'1'，但在您的樣本輸出中不存在（它絕對是子序列並重復）。 – n0rd

不是一個友好的面試問題 - 這是意味着 – mohsenmadi

我覺得你說的而不是不一定是連續的子序列約連續子陣列。你的解決方案是O（n^3）。你可以使用後綴樹，它允許你在O（n）中找到重複的子數組。

2015-06-15 19:05:21 real

子字符串和子序列是完全不同的.OP是問打印子序列。 – Ankur

@Shan：「subsequence」的確是OP使用的詞，但是根據他/她給出的例子，他/她的意思是「substring」。 –

回答