Codeforces 432D 完美子串（kmp+dp or 后缀树组）

╰半橙微兮° 2021-10-18 08:40 286阅读 0赞

## 题意：给出一个字符串，求所有既是前缀串又是后缀串的字符串出现了几次。 ##

## 分析：考察对next数组的理解。 ##

## 参考[https://blog.csdn.net/huanghongxun/article/details/53209004][https_blog.csdn.net_huanghongxun_article_details_53209004]、[https://blog.csdn.net/hfl030/article/details/79858464][https_blog.csdn.net_hfl030_article_details_79858464]、[https://www.cnblogs.com/dabai520/p/7554166.html][https_www.cnblogs.com_dabai520_p_7554166.html]。 ##

## 总结：字符串很久没碰了，很多算法思想都忘了，这两天开专题补回来。 ##

## 代码（kmp+dp）： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e6+5;
    char s[N];
    int lens,ans,nt[N],d[N];
    bool f[N];//f[i]表示长度为i的前缀子串是否合法。
    
    void init(){
        memset(nt,0,sizeof(nt));
        int j=0;
        for(int i=2;i<=lens;++i){
            while(j&&s[i]!=s[j+1]) j=nt[j];
            if(s[i]==s[j+1]) ++j;
            nt[i]=j;
        }
    }
    
    void dfs(int i){
        if(!i) return;
        ++ans;f[i]=1;
        dfs(nt[i]);
    }
    
    void work(){
        init();
        memset(d,0,sizeof(d));
        for(int i=1;i<=lens;++i) d[i]=1;
        for(int i=lens;i>=1;--i) d[nt[i]]+=d[i];
        ans=0;
        memset(f,0,sizeof(f));
        dfs(lens);
        printf("%d\n",ans);
        for(int i=1;i<=lens;++i) if(f[i]) printf("%d %d\n",i,d[i]);
    }
    
    int main(){
        scanf("%s",s+1);
        lens=strlen(s+1);
        work();
        return 0;
    }

[https_blog.csdn.net_huanghongxun_article_details_53209004]: https://blog.csdn.net/huanghongxun/article/details/53209004
[https_blog.csdn.net_hfl030_article_details_79858464]: https://blog.csdn.net/hfl030/article/details/79858464
[https_www.cnblogs.com_dabai520_p_7554166.html]: https://www.cnblogs.com/dabai520/p/7554166.html