首页技术正文

POJ 2752 (kmp求所有公共前后缀长度)

开发者奕玮技术 2022年11月14日

0 收藏 348 点赞 4,839 浏览 821 个字

<题目链接>

<转载于>

题目大意：

给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。即输出该字符串所有前缀后缀相等的子串的长度。

解题分析：

如左图，假设黑色线来代表字符串str，其长度是len，红色线的长度代表next[len]，根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同（也就是两条线所对应的位置）。我们再求出next[len]位置处的next值，也就是图中蓝线对应的长度。同样可以得到两个蓝线对应的子串肯定完全相同，又由于第二段蓝线属于左侧红线的后缀，所以又能得到它肯定也是整个字符串的后缀。

所以对于这道题，求出len处的next值，并递归的向下求出所有的next值，得到的就是答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int M =4e5+;
char s[M];
int nxt[M];
void getnext(){
    int i=,j=-;
    nxt[]=-;
    while(s[i]){
        if(j==-||s[i]==s[j]){
            nxt[++i]=++j;
        }
        else j=nxt[j];
    }
}
int main(){
    while(gets(s)){
        getnext();
        int len=strlen(s);
        int res=len;
        int cnt=,output[M];
        while(nxt[res]>){     //按上面分析的方式转移
            output[++cnt]=nxt[res];
            res=nxt[res];
        }
        sort(output+,output++cnt);
        for(int i=;i<=cnt;i++){
            printf("%d ",output[i]);
        }
        printf("%d\n",len);
    }
    return ;
}