[BZOJ 1511]Periods of Words

danihao123 posted @ 2016年9月15日 17:59 in 题解 with tags KMP POI bzoj 循环节问题 , 340 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数,然后对于每个失配函数沿着失配边往前一直走(不能走到0)。然后对于每个前缀[tex]i[/tex],答案就是[tex]i-f[i][/tex](要求[tex]f[i][/tex]不为0,反之无解)。

为什么这样可以呢?

首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀,如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串,这个子串是不考虑的。当然,我们希望在这个被删除的子串最短辣。

代码:

/**************************************************************
    Problem: 1511
    User: danihao123
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:5704 kb
****************************************************************/
 
#include <cstdio>
const int maxn=1000005;
 
char buf[maxn];
int f[maxn];
int main(){
    register int i,j;
    register long long ans=0;
    int n;
    scanf("%d%s",&n,buf);
    f[0]=f[1]=0;
    for(i=1;i<n;i++){
        j=f[i];
        while(j && buf[i]!=buf[j])
            j=f[j];
        f[i+1]=(buf[i]==buf[j]?j+1:0);
    }
    for(i=2;i<=n;i++){
        if(f[i]){
            while(f[f[i]]){
                f[i]=f[f[i]];
            }
        }
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            ans+=i-f[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter