找到最长的重复字符串，并将其重复给定的字符串中的次数 [英] Find the longest repeating string and the number of times it repeats in a given string

问题描述

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

这篇关于找到最长的重复字符串，并将其重复给定的字符串中的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！