例如，指定字符串 ABC FGHI BC KL ABCD LKM ABCDEFG ，该函数将返回字符串 ABCD 和2计数

For example, given string "abc fghi bc kl abcd lkm abcdefg", the function should return string "abcd" and the count of 2.

AO（N ^ 2）解决方案似乎很容易，但我在寻找一个更好的解决方案。

A O(n^2) solution seems easy but I am looking for a better solution.

编辑：如果没有更好的比为O（n ^ 2）有可能比它的方法是最佳的性能明智

Edited: If nothing better than O(n^2) is possible than which approach would be best performance wise.

推荐答案

您可以在线性时间内通过构建的后缀树，并采取从根到最深的内部节点的路径;这会给你时间最长重复的字符串。一旦你有一个字符串，它是微不足道的计算中出现。

You can solve this in linear time by building a suffix tree and taking a path from the root to the deepest internal node; this will give you the longest repeated string. Once you have that string, it's trivial to count the number of times it appears.