自动搬运

查看原文

来自洛谷，原作者为

	LYYY 什么都超菜，这个家伙留下了个寂寞

搬运于2025-08-24 21:59:41，当前版本为作者最后更新于2019-02-15 21:53:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

刚学了KMP算法见到这道题，完全没有思路，但是真的想出来了之后，真的对KMP算法中的next数组有了更深的认识。

按照题意，读入字符串长度n和字符串ss ；

这道题求的是字符串ss最小长度的循环，我们称之为“ss的循环子串”，首先引入结论：

ans=n-next[n]

现在解释为什么答案是 n-next[n] ：

一、 先求出next数组（其实只求出next[n]就行了），即求出字符串的最大公共前后缀；

假设这两段是整个字符串ss的最大公共前后缀；

第一段： 1~next[n]

第二段： n-next[n]+1~n

为了方便观察，我将前缀和后缀分开，令它们上下一一对应；

二、 现在我们人为地把字符串按照红色段的长度划分为若干段并标号（图中的第1,2,3,4,5,6,7,8,9段）；

容易看出，红色的一段和后缀合起来就是原字符串；

所以推出：

1. 因为上下对应相等，故第1段等于红色段；

2. 因为是公共前后缀，故第2段等于第1段；

3. 因为上下对应相等，故第3段等于第2段；

4. 因为是公共前后缀，故第4段等于第3段；

5. ......

6. 红色段就是循环子串；

三、从而，我们知道了原字符串ss除去公共前后缀（图中的黑色段）中的一个剩下的就是循环子串（图中的红色段）；同样，易知原串ss除去开头（或结尾）的循环子串（图中的红色段）剩下的部分就是公共前后缀（图中的黑色段）。

至此，问题中要求的原字符串ss的最小循环子串，就转化成了求原字符串ss的最大公共前后缀；

因此，有 ans=n-next[n] 。

AC代码（kmp数组即next数组）

#include<cstdio>
using namespace std;
const int maxn=1111111;
int n,kmp[maxn];//kmp数组即next数组
char ss[maxn];
int main()
{
	scanf("%d%s",&n,ss+1);
	int j=0;
	for(int i=2;i<=n;++i)
	{
		while(j&&ss[i]!=ss[j+1]) j=kmp[j];
		if(ss[i]==ss[j+1]) ++j;
		kmp[i]=j;
	}
	printf("%d",n-kmp[n]);
	return 0;
}

谢谢阅览