Passward

问题 A: Passward

时间限制: 1 Sec 内存限制: 512 MB

题目描述

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

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

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

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

输入格式：

仅一行，字符串 s。

输出格式：

如题所述

样例输入

fixprefixsuffix

样例输出：

fix

数据范围：

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

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

这道题和之前的题目名字好像啊(ˇˍˇ) ～，差点打错了。。

想不到我也有考试1A的一天，一道挺水的题，直接打哈希了。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 const int P=127;
 8 vector<int>v;
 9 char s[100005];
10 unsigned long long ha[100005],xp[100005];
11 int ss;
12 void get_hash(char *s){
13     memset(xp,0,sizeof(xp));
14     xp[0]=1;
15     for(int i=ss-1;i>=0;--i)
16         ha[i]=ha[i+1]*P+s[i]-'a';
17     for(int i=1;i<=ss;++i)
18         xp[i]=xp[i-1]*P;
19 }
20 bool judge(int len){
21     if(s[ss-1]!=s[len-1]) return false;
22     long long ans1=ha[0]-ha[len]*xp[len];
23     long long ans2=ha[ss-len];
24     if(ans1!=ans2) return false;
25     for(int i=0;i<v.size();++i){
26         int o=v[i];
27         if(o+len<ss){
28             long long ans3=ha[o]-ha[o+len]*xp[len];
29             if(ans3==ans1)  return true;
30         }
31         else return false;
32     }
33     return false;
34 }
35 int main(){
36     scanf("%s",s);ss=strlen(s);
37     get_hash(s);if(ss<=2) ss=2;
38     for(int i=1;i<ss;++i)
39         if(s[i]==s[0])
40             v.push_back(i);
41     int tmp=0;
42     for(int i=ss-2;i;--i){
43         if(judge(i)){
44             tmp=i;
45             break;
46         }
47     }
48     if(!tmp) printf("Just a legend");
49     else for(int i=0;i<tmp;++i) cout<<s[i];
50     return 0; 
51 }

听说正解是KMP??