2021.11.09 P3435 [POI2006]OKR-Periods of Words（KMP)

https://www.luogu.com.cn/problem/P3435

题意：

对于一个仅含小写字母的字符串 a，p 为 a 的前缀且 p不等于a，那么我们称 p 为 a的 proper 前缀。

规定字符串 Q（可以是空串）表示 a的周期，当且仅当 Q是 a的 proper 前缀且 a是 Q+Q 的前缀。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

分析：

https://ofnoname.blog.luogu.org/solution-p3435

nexti数组存的是最长的前缀与后缀的公共前缀！

代码如下：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6+10;

typedef long long ll;

ll ans;

int n,nexti[N];

char s[N];

int main(){

	cin>>n;

	scanf("%s",s);

	int k=-1;

	nexti[0]=-1;

	for(int i=0;i<n;){

		while(s[i]!=s[k]&&k!=-1)k=nexti[k];

		if(s[i]==s[k]||k==-1)nexti[++i]=++k;

	}

	//for(int i=1;i<=n;i++)cout<<nexti[i]<<" ";cout<<endl;

	for(int i=2,j=2;i<=n;i++,j=i){

		while(nexti[j])j=nexti[j];

		if(nexti[i])nexti[i]=j;

		ans+=i-j;

	}

	cout<<ans;

	return 0;

}

巴特西

2021.11.09 P3435 [POI2006]OKR-Periods of Words（KMP)

2021.11.09 P3435 [POI2006]OKR-Periods of Words（KMP)

最新文章

热门文章