c++ - 在 C++ 中的字符串中查找循环的有效算法和代码？

Question

例如，在“12345123451234512345”中，找到“12345”的高效算法是什么？

用 C++ 编码。

谢谢。

Answer 1

继续你的例子:

12345123451234512345 返回 12345

我想你想要的是找到最长的针，重复完成大海捞针，即 1212121212 => 12, 444 => 4 等等。

最简单的解决方案是选择第一个字符并运行整个字符串比较匹配项。如果在任何时候你有一个不匹配，选择前两个字符并运行整个字符串比较等等，直到你的窗口大小变得大于字符串的一半。

复杂度应该是 O(n^2)

您可以根据字符串的长度优化选择的窗口大小，即窗口大小只能是字符串长度的约数。