对于长度为L的字符串,我想找到在字符串中出现n(n <L)或更多次的最长子字符串.
例如,在"BANANA"中出现2次或更多次的最长子字符串是"ANA",一旦从索引1开始,并且再次从索引3开始.允许子字符串重叠.
在字符串"FFFFFF"中,出现3次或更多次的最长字符串是"FFFF".
n = 2的强力算法将选择字符串中的所有索引对,然后一直运行直到字符不同.运行部分采用O(L)并且对的数量是O(L ^ 2)(不允许重复,但我忽略了这一点)因此该算法对于n = 2的复杂度将是O(L ^ 3).对于更大的n值,这会呈指数增长.
这个问题有更有效的算法吗？