danihao123's Blog

循环节又一题……用KMP性质搞搞即可。

注意特判（好像是句废话），再就没啥了……

代码：

#include <cstdio>
#include <cstring>
const int maxn=1e6+5;
char P[maxn];
int f[maxn];
int main(){
	register int i,j,xhj,n;
	while(scanf("%s",P)){
		if(P[0]=='.')
			break;
		n=strlen(P);
		f[0]=f[1]=0;
		for(i=1;i<n;i++){
			j=f[i];
			while(j && P[j]!=P[i])
				j=f[j];
			f[i+1]=(P[j]==P[i]?j+1:0);
		}
		xhj=n-f[n];
		if(!(n%xhj)){
			printf("%d\n",n/xhj);
		}else{
			puts("1");
		}
	}
	return 0;
}

很妙的一道题啊。

这个题可以先求一遍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;
}

KMP处女作……

然而这题只用得着失配函数= =

话说常见的OI考试中考KMP好像就只有考循环节问题的了= =

代码：