P3435 [POI 2006] OKR-Periods of Words

题目描述

一个字符串是由小写英文字母组成的有限序列。特别地，它也可以是空序列（即长度为 $0$ 的序列）。

如果字符串 $A$ 是通过字符串 $B$ 和 $C$ 按顺序连接（中间没有任何间隔符号）得到的，我们表示为 $A=BC$。

如果存在一个字符串 $B$ 使得 $A=PB$，那么字符串 $P$ 是字符串 $A$ 的前缀。此外，如果 $P\ne A$ 且 $P$ 不是空字符串，我们称 $P$ 是 $A$ 的真前缀。

如果 $Q$ 是 $A$ 的真前缀，并且 $A$ 是字符串 $QQ$ 的前缀（不一定是真前缀），那么字符串 $Q$ 是 $A$ 的周期。例如，字符串 abab 和 ababab 都是 abababa 的周期。

字符串 $A$ 的最大周期是其最长的周期，如果 $A$ 没有周期，则为空字符串。例如，ababab 的最大周期是 abab；abc 的最大周期是空字符串。

任务：

编写一个程序，计算该字符串所有前缀的最大周期长度之和。

输入格式

第一行包含一个整数 $k$，表示字符串的长度。

接下来的一行包含一个由 $k$ 个小写英文字母组成的字符串。

输出格式

单独一行输出一个整数，表示输入字符串所有前缀的最大周期长度之和。

输入输出样例 #1

输入 #1

8
babababa

输出 #1

24

说明/提示

（由 Gemini 2.5 Flash 翻译，人工审核）

数据范围

对于所有数据，$1\le k\le 10^6$。

C++实现

#include <bits/stdc++.h>
#define MAX (1000000+50)
using namespace std;

int size,nxt[MAX];
char s[MAX];
unsigned long long ans;//记得开long long

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cin>>size>>(s+1);
	for (register int i=2,j=0; i<=size; i++)
	{
		while (j && s[i]!=s[j+1]) j=nxt[j];
		if (s[i]==s[j+1]) j++; nxt[i]=j;
	}//KMP求解next数组
	for (register int i=2,j=2; i<=size; i++,j=i)
	{
		while (nxt[j]) j=nxt[j]; //递推求最短匹配长度
		if (nxt[i]) nxt[i]=j; //修改next[i]的值
		ans+=i-j;//统计答案
	}
	cout<<ans<<endl;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容