首页 > 代码库 > hust 1589 找出子串

hust 1589 找出子串

2024-07-08 07:09:04   219人阅读

题目描述

给定一个字符串s ，求出一个子串t，满足如下性质：
1.       t是s的一个前缀。
2.       t是s的一个后缀。
3.       t出现在s的中间（并非前缀和后缀）。
例如：
字符串s为fixprefixsuffix，t可以是fix。
字符串s为aaa，t可以是aa。
输入

输入包括多组数据，每组数据为一行，每行有一个字符串s，其长度不超过10^6（一百万）。

输出

每组数据输出一行，每行为一个字符串t，若不存在字符串t，则输出"Just a legend"（不包括引号）。样例输入

fixprefixsuffixabcdabc

样例输出

fixJust a legend

很经典的一道KMP算法题目，求是前缀又是后缀的字串，再判断是否出现在中间，很简单，有kmp判断，再用dp判断是否出现的次数大于2，这样就可以了，
题目aaa那个不对，还有就是这个题要求输出最长的，题目没有说清楚，WA了两次，真是晕
#include<iostream>#include<cstdio>#include<cstring>#include<string>using namespace std;const int maxn=1000000+10;char p[maxn];int f[maxn],dp[maxn],a[maxn];void getf(){    int m=strlen(p);    f[0]=f[1]=0;    for (int i=1;i<m;i++)    {        int j=f[i];        while(j && p[i]!=p[j]) j=f[j];        f[i+1]=(p[i]==p[j]?j+1:0);    }}int main(){    int n;    bool flag;    while(scanf("%s",p)!=EOF)    {        getf();        //for (int i=1;i<=strlen(p);i++) printf("%d ",f[i]);        //printf("\n");        memset(dp,0,sizeof(dp));        int L=strlen(p);        int k=L;n=0;        while(f[k])        {            if (f[k]) a[n++]=f[k];            k=f[k];        }        //for (int i=0;i<n;i++) printf("%d ",a[i]);        //printf("\n");        for (int i=L;i>=0;i--)        {            dp[i]++;            dp[f[i]]+=dp[i];        }        flag=false;        for (int i=0;i<n;i++)        {            if(dp[a[i]]>=3)            {                flag=true;                for (int j=0;j<a[i];j++) printf("%c",p[j]);                printf("\n");                break;            }        }        if (!flag) printf("Just a legend\n");    }    return 0;}

作者 chensunrise


联系
我们