首页 > 代码库 > Password

Password

题面:

Password

【题目描述】

你来到了一个庙前,庙牌上有一个仅包含小写字母的字符串 s。

传说打开庙门的密码是这个字符串的一个子串 t,并且 t 既是 s 的前缀又是 s 的后缀并且还在 s 的中间位置出现过一次。

如果存在这样的串,请你输出这个串,如有多个满足条件的串,输出最长的那一个。

如果不存在这样的串,输出"Just a legend"(去掉引号)。

【输入格式】

仅一行,字符串 s。

【输出格式】

如题所述

【样例输入】

fixprefixsuffix

【样例输出】

fix

【数据范围】

对于 60%的数据, s 的长度<=100

对于 100%的数据, s 的长度<=100000

 

先求出next数组,之后记录1~n-1中那些next出现过,从n一直向前跳next,跳到出现过就是答案。

技术分享
 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 #define min(a,b) a<b?a:b 5 #define maxn 100001 6 char s[maxn]; 7 int l,nx[maxn]; 8 bool vis[maxn]; 9 void init()10 {11     int i,j=0;12     for(i=1;i<l;i++)13     {14         while(j&&s[i]!=s[j])15             j=nx[j];16         if(s[i]==s[j])17             ++j;18         nx[i+1]=j;19     }20 }21 int main()22 {23     scanf("%s",s);24     l=strlen(s);25     init();26     int i;27     for(i=1;i<l;i++)28         vis[nx[i]]=true;29     for(i=nx[l];i;i=nx[i])30         if(vis[i])31             break;32     if(i==0)33         printf("Just a legend");34     else35         for(int j=0;j<i;j++)36             putchar(s[j]);37 }
Password

 

Password