[POI2006]Periods of Words

题目大意：
　　给定一个长度为$n(n\leq10^6)$的字符串$S$，定义一个串$S$的最大周期为一个不为$S$的字符串$Q$，满足$Q$为$S$的前缀且$S$为$QQ$的前缀。求字符串$S$的每一个前缀的最大周期长度之和。

思路：
　　KMP+DP。
　　不难发现串$S$去掉前缀串$Q$后，剩下的串是$Q$的最短非空前缀。首先用KMP算法求出$next$数组。然而$next$求出来是最长，要让它变成最短，需要用DP的思想，向前找到最初的非0$next$对应的长度$f_i$，最后求$\sum(i-f[i])$即可。

 #include<cstdio>

 typedef long long int64;

 const int N=1e6+;

 char s[N];

 int n,next[N],f[N];

 int main() {

     scanf("%d%s",&n,s);

     for(register int i=,j=next[]=-;i<n;next[++i]=++j) {

         while(~j&&s[i]!=s[j]) j=next[j];

     }

     int64 ans=;

     for(register int i=;i<=n;i++) {

         f[i]=next[i]?f[next[i]]:i;

         ans+=i-f[i];

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

[POI2006]Periods of Words

最新文章

热门文章