4
例如，在重複的次數，給定的字符串「ABC FGHI BC KL ABCD LKM ABCDEFG」，函數應該返回字符串「ABCD」和計數2.查找最長的重複字符串，並將其給定的字符串
AO（n^2）解決方案似乎很容易，但我正在尋找更好的解決方案。
編輯：如果沒有比O（n^2）更好的方法，那麼哪種方法最適合表現明智。
A
回答
9
您可以在線性時間內通過建立suffix tree，並採取從根到最深的內部的路徑解決這個節點;這會給你最長的重複字符串。一旦你有了這個字符串，計算它出現的次數是微不足道的。
2
一個狀態機可能會提供比大O（N^2）更好的東西。
編輯：後綴樹在對方的回答提出的一種狀態機:)的這樣一個實現
相關問題
- 1. 查找重複字符的最長的子字符串中的
- 2. 查找給定字符串中的所有非重複字符
- 3. 查找字符串中最長重複子字符串所需的Java函數？
- 4. 一個給定的字符串中查找字符串模式的重複
- 5. 查找字符串C＃字符的最發生，返回最長的復現字符的字符串
- 6. 查找給定字符串中的所有重複子字符串
- 7. 查找字符串數組中最長的字符串
- 8. 實用程序查找最長可能重複的字符串
- 9. 從給定的字符串給定長度的字符的差異字符串
- 10. 查找字符串中重複子字符串的數量
- 11. 查找字符串的字符串w /最低頻字符
- 12. 查找給定字符串中的重複模式
- 13. 在Python中以字符串的數字順序查找最長的字符串
- 14. 查找字符串中的字符串
- 15. 如何查找給定字符串中的特定字符？
- 16. 如何找到給定字符串中最長的迴文？
- 17. Java：如何找到給定字符串中最長的單詞？
- 18. jQuery - 查找字符串並將字符串前置到它？
- 19. 查找最長字符串的索引並返回該索引？
- 20. 找到最長的字符串前綴
- 21. 查找長度爲N的重複子字符串
- 22. 在字符串python中查找最長的唯一子字符串
- 23. 查找最小長度子字符串包含所有的字符串
- 24. SQL：在字符串中查找連續的重複字符
- 25. 索引列表查找字符串中的重複字符（Python）
- 26. 如何查找和打印字符串上的重複字符？
- 27. 最長的子字符串
- 28. 最長的字符串
- 29. 將可變長度字符串分配給固定長度字符串
- 30. 查找包含其自身長度的字符串的長度？
你的SO用戶名是有點放棄。 – 2010-01-31 14:35:45
這是故意避開SNOBS。 – 2010-01-31 14:38:18
最長的重複子字符串問題：http://en.wikipedia.org/wiki/Longest_repeated_substring_problem – sambowry 2010-01-31 14:44:45