返回首页 返回专题

【CF432D】Prefixes and Suffixes 题解

构造出给定串的next数组

然后从next[n]出发，沿next数组往回跳，沿途经过的位置就是题中提到的串

串的出现次数可以由DP求得，其转移方程为：

• f[p]=sigma{f[s]}+1,(next[s]=p)

然后不要忘记还有给定串本身

#include<bits/stdc++.h>
using namespace std;

char s[100010];
int nxt[100010];
int r[100010],cnt=0;
int f[100010];

int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1),j=0;
	for(int i=2;i<=n;i++)
	{
		while(j&&s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) j++;
		nxt[i]=j;
	}
	for(int i=nxt[n];i;i=nxt[i]) r[++cnt]=i;
	cout<<cnt+1<<endl;
	for(int i=n;i>=1;i--) f[i]++,f[nxt[i]]+=f[i];
	for(int i=cnt;i>=1;i--) printf("%d %d\n",r[i],f[r[i]]);
	printf("%d %d\n",n,1);
	return 0;
}