首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。