BZOJ 1511 [POI2006]OKR

题意: 求一个串的所有前缀的最长周期长度之和，特别的，，周期为自己的串的最长周期长度视作0. 解析: 直接求一下next，之后把所有的next向前找到最后一个非零地方的Next。 然后扫一遍对于每个next非零位置的周期来说就是i-new_next[i] 还是之前的那个性质，n-next[i]是最小循环周期，推一下就变成最长了。 代码:

using namespace std;typedef long long ll;int n;int ne[N];char s[N];void getnext(){ne[0]=-1;int i=0,j=-1;while(i<n){if(j==-1||s[i]==s[j]){i++,j++;ne[i]=j;}else j=ne[j];}}int main(){#ifndef ONLINE_JUDGEfreopen(“1511.in”,”r”,stdin);freopen(“1511.out”,”w”,stdout);#endifscanf(“%d”,&n);scanf(“%s”,s);getnext();ll ans=0;for(int i=1;i<=n;i++){if(!ne[i])continue;while(ne[ne[i]])ne[i]=ne[ne[i]];}for(int i=1;i<=n;i++){if(ne[i]!=0)ans+=i-ne[i];}printf(“%lld\n”,ans);#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);#endif}

就得加倍付出汗水，赢得场场精彩