查找字符串中重叠和非重叠子字符串的数目

Question

注：这不是How to find the overlap between 2 sequences, and return it的副本

[尽管我希望上述方法能适用于以下问题]

问：虽然我做对了，但它仍然不是一个可扩展的解决方案，而且绝对没有优化（分数很低）。请阅读以下对问题的描述，并提供更好的解决方案。在

问题：

为了简单起见，我们要求前缀和后缀非空且短于整个字符串S。字符串S的边框是同时是前缀和后缀的任何字符串。例如，"cut"是字符串"cutletcut"的边框，而字符串"barbararhubarb"有两个边框："b"和{}。在

class Solution { public int solution(String S); }

如果给定一个由N字符组成的字符串S，则返回其在给定字符串中至少有三个不重叠的最长边框的长度。如果S中没有这样的边框，则函数应返回0。在

例如

• 如果S = "barbararhubarb"函数应该返回1，如上所述
• 如果S = "ababab"函数应该返回2，因为"ab"和{}都是{}的边界，但是只有{}有三个不重叠的出现
• 如果S = "baaab"函数应该返回0，因为它唯一的边界"b"只出现两次。在

假设：

• N是[0..1,000,000]范围内的整数
• 字符串S只包含小写字母（a−z）。在

复杂性：

• 预期的最坏情况时间复杂度为O(N)
• 预期的最坏情况空间复杂性为O(N)（不计算输入参数所需的存储空间）。在

^{pr2}$

我的解的时间复杂性是：O（N2）或O（N4） 非常感谢帮助。在

Answer 1

我的解决方案是结合Rabin-Karp和Knuth-Morris-Pratt算法。 http://codility.com/cert/view/certB6J4FV-W89WX4ZABTDRVAG6/details

Answer 2

我有一个后缀数组的解决方案（实际上有一种算法可以在线性时间或更糟糕的时间内构造SA和LCP，但肯定不是二次的）。在

仍然不确定是否可以不使用RMQs（O（logn）和segmentree），我无法通过我自己的案例，看起来相当复杂，但有了RMQs，它可以（不提使用for循环而不是RMQ的方法，这会使它成为二次方的）。在

解决方案是执行速度相当快，通过了我的21个测试用例，我已经设法设计了各种各样的特权，但仍然失败的一些案例。不确定这是否对你有帮助，或者让你知道如何解决这个问题，但我确信，像@Vicenco在他的一些评论中所说的那样，这种天真的解决方案不会比Silver更好。在

编辑： 设法解决了所有的问题，但还是慢了下来。我不得不强制执行一些条件，但不得不增加复杂性，仍然不确定如何优化。会随时通知你的。祝你好运！在

Answer 3

尽管如此，还是有一个不同的解决方案

几乎所有的字母都一样 aaaaa…aa？？aaaa？？。。。。aaaaaaaa 2.150秒。超时错误 运行时间：2.15秒，时限：1.20秒。在

两个字母都相同，2.120秒超时错误 运行时间：2.12秒，时限：1.24秒。在

编辑：搞定了！ 现在我有了一个在O（N）中执行的解决方案，它通过了100/100结果的所有检查：） 我不知道代码，但它是一个很好的工具！在