好吧，这个问题肯定可以在 O(n) 内解决，我们只需要按照你的建议巧妙地使用 KMP 即可。
解决最长的正确前缀，这也是一个后缀问题是我们将使用的 KMP 的重要组成部分。
The 最长的正确前缀，这也是一个后缀问题有点拗口，所以我们就称它为前缀后缀问题目前。
The 前缀后缀问题可能很难理解，所以我将举一些例子。
“abcabc”的前缀后缀解决方案是
“abc”，因为这是最长的字符串，也是正确的前缀
和一个正确的后缀（正确的前缀和后缀不能是整个
细绳）。
“abcabca”的前缀后缀解决方案是“a”
嗯嗯嗯嗯等一下，如果我们只是从“abcabc”末尾砍掉“a”，我们就会留下“abcabc”，如果我们得到这个新字符串的解决方案（“abc”）并再次砍掉它，我们就会留下“ abc"嗯嗯嗯嗯。非常有趣。（这几乎是解决方案，但我将讨论为什么它有效）
好吧，让我们尝试进一步形式化这种直觉，看看是否能找到解决方案。
我将在我的论证中使用一个关键假设：
我们的模式的最小周期是我们模式中每个较大周期的有效周期
让我们存储第一个的前缀后缀解决方案i我们的模式的字符lps[i]. This lps数组可以计算为O(n)它用于 KMP 算法，您可以阅读有关如何计算它的更多信息O(n) here: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
为了让我们清楚，我将列出一些例子lps arrays
模式：“aaaaa”
lps: [0, 1, 2, 3, 4]
模式：“aabbcc”
lps: [0, 1, 0, 0, 0, 0]
模式：“abcabcabc”
lps: [0, 0, 0, 1, 2, 3, 4, 5, 6]
好吧，现在让我们定义一些变量，来帮助我们找出为什么会这样lps数组很有用。
Let l是我们模式的长度，让k是 lps 数组中的最后一个值（k=lps[l-1])
价值k告诉我们第一个k我们的字符串的字符与最后一个相同k我们的字符串的字符。我们可以利用这个事实来找到一个时期！
使用此信息，我们现在可以显示由第一个组成的前缀l-k我们的字符串的字符形成一个有效周期。这很清楚，因为接下来k不在我们的前缀中的字符必须与第一个字符匹配k我们的前缀字符，因为我们如何定义我们的lps大批。首先k我们的前缀中的字符必须与最后一个相同k构成我们后缀的字符。
在实践中，您可以使用简单的 while 循环来实现此目的，如下所示，其中index标记您当前认为是最小句点的后缀的结尾。
public static void main(String[] args){
String pattern="abcabcabcabca";
int[] lps= calculateLPS(pattern);
//start at the end of the string
int index=lps.length-1;
while(lps[index]!=0){
//shift back
index-=lps[index];
}
System.out.println(pattern.substring(0,index+1));
}
并且自从计算lps发生在O(n)，并且您总是在 while 循环中至少后退 1 步，整个过程的时间复杂度很简单O(n)
如果您想查看下面的确切代码，我在我的calculateLPS()方法中大量借鉴了KMP的geeksForGeeks实现，但我建议您也看看他们的解释：https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
static int[] calculateLPS(String pat) {
int[] lps = new int[pat.length()];
int len = 0;
int i = 1;
lps[0] = 0;
while (i < pat.length()) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = len;
i++;
}
}
}
System.out.println(Arrays.toString(lps));
return lps;
}
最后但并非最不重要的一点是，感谢您发布如此有趣的问题，弄清楚它非常有趣！另外，我对此很陌生，所以如果我的解释的任何部分没有意义，请告诉我。
