很好的一道题，巧用kmp，我是绕了好久,想出来思路但是没结合hash优化，超时
代码语言：javascript复制#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char ch[1000005];
int next[1000005];
int hash[1000005];
void getnext()
{
int len=strlen(ch);
int i=0,j=-1;
next[0]=-1;
while(i<len)
{
if(j==-1 || ch[i]==ch[j])
{
i ;
j ;
next[i]=j;
hash[j] ; //hash表统计长度为j的子串数目
}
else
j=next[j];
}
}
int main()
{
while(cin>>ch)
{
int len=strlen(ch);
memset(hash,0,sizeof(hash));
getnext();
int i=len;
int flag=0;
hash[next[len]]--;
while(next[i]) //如果没有找到最长的，就在next【len】的长度里继续找，直到长度为0才可以认为没有
{
if(hash[next[i]]) //一开始没有用hash，每一遍都在匹配。结果肯定超时
{
flag=1;
break;
}
else
{
next[i]=next[next[i]];
}
}
if(!flag)
cout<<"Just a legend"<<endl;
else
{
for(int j=0;j<next[i];j )
cout<<ch[j];
cout<<endl;
}
}
return 0;
}。
