题解 CF432D 【Prefixes and Suffixes】

世末OIer · 2019-02-07 17:36:42 · 题解

Z-function (因该首先想到的不是它吧)

#include<bits/stdc++.h>
using namespace std;
char s[111111];
int l,r,i,j,k,cnt,n,z[111111],ans[111111];
pair<int,int> res[111111];
int main(){
    scanf("%s",s);
    n=strlen(s);
    l=0,r=0,z[0]=n;
    for(i=1;i<n;++i){                        //计算出所有的z的值
        if(i>r){
            j=0;
            while(s[j]==s[i+j]) ++j;
            l=i,r=i+j-1,z[i]=j;
        }else{
            k=i-l;
            if(z[k]<r-i+1) z[i]=z[k];
            else{
                j=r;
                while(s[j]==s[j-i]) ++j;
                l=i,r=j-1,z[i]=r-l+1;
            }
        }
    }
    for(i=0;i<n;++i) ++ans[z[i]];           //统计个数
    for(i=n-1;i;--i) ans[i]+=ans[i+1];
    for(i=0;i<n;++i) if(i+z[i]==n) res[++cnt]=make_pair(z[i],ans[z[i]]);
    sort(res+1,res+cnt+1);                  //按照要求排个序
    printf("%d\n",cnt);
    for(i=1;i<=cnt;++i) printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}