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的一天，一道挺水的题，直接打哈希了。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int P=;

 vector<int>v;

 char s[];

 unsigned long long ha[],xp[];

 int ss;

 void get_hash(char *s){

     memset(xp,,sizeof(xp));

     xp[]=;

     for(int i=ss-;i>=;--i)

         ha[i]=ha[i+]*P+s[i]-'a';

     for(int i=;i<=ss;++i)

         xp[i]=xp[i-]*P;

 }

 bool judge(int len){

     if(s[ss-]!=s[len-]) return false;

     long long ans1=ha[]-ha[len]*xp[len];

     long long ans2=ha[ss-len];

     if(ans1!=ans2) return false;

     for(int i=;i<v.size();++i){

         int o=v[i];

         if(o+len<ss){

             long long ans3=ha[o]-ha[o+len]*xp[len];

             if(ans3==ans1)  return true;

         }

         else return false;

     }

     return false;

 }

 int main(){

     scanf("%s",s);ss=strlen(s);

     get_hash(s);if(ss<=) ss=;

     for(int i=;i<ss;++i)

         if(s[i]==s[])

             v.push_back(i);

     int tmp=;

     for(int i=ss-;i;--i){

         if(judge(i)){

             tmp=i;

             break;

         }

     }

     if(!tmp) printf("Just a legend");

     else for(int i=;i<tmp;++i) cout<<s[i];

     return ;

 }

听说正解是KMP??