找到最长的重复字符串，并将其重复给定的字符串中的次数

本文介绍了找到最长的重复字符串，并将其重复给定的字符串中的次数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

例如，指定字符串 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.