http://acm.hdu.edu.cn/showproblem.php?pid=4763
http://codeforces.com/problemset/problem/126/B
这两个题都是在考察next的应用。区别在于一个是不能有重叠，一个是可以有重叠。
一级条件，前后缀都存在；二级条件 在之前存在前后缀。
对于可以重叠的，很简单，利用next记录一下前缀后缀都存在的那些点，然后跑一遍循环找一下这些满足一级条件的哪些满足二级条件，就ok了。
不可以重叠的，其实就是加了一个零级条件，判断长度，还有一个四级条件，还是长度。
还是有收获的。
对于next理解又多了一点，标注next其实就是标注这个位置之前是否满足前后缀一样。满足就美滋滋了。
贴代码，具体体会一下
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(s1) memset(s1,0,sizeof(s1))
#define meminf(s1) memset(s1,0x3f,sizeof(s1))
#define ll long long
using namespace std;
int nex[],l1,l2;
void getn(int n,char c[])
{
int i=,j=-;
nex[]=-;
while(i<n)
{
if(j==-||c[i]==c[j])
{
i++;j++;nex[i]=j;
}
else j=nex[j];
}
return;
}
int f[];
int main()
{
int t;
cin>>t;
char s[];
while(t--)
{
scanf("%s",s);
int l=strlen(s);
getn(l,s);
mem0(f);
int tmp=l;
while(tmp>)
{
if(l>=*tmp) f[tmp]=;
tmp=nex[tmp];
}
int ans=;
for(int i=l-;i>;i--)
{
tmp=i;
while(tmp>){
if(f[tmp]&&i>=*tmp&&l>=tmp+i)
{
ans=max(ans,tmp);break;
}
tmp=nex[tmp];
}
}
cout<<ans<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
#define mem0(a) memset(a,0,sizeof a)
#define ll long long
int nxt[],vis[];
inline void getn(int len,char s[])
{
int i,j;
nxt[]=-;
for (i=;i<len;++i)
{
j=nxt[i];
while (j!=-&&s[j]!=s[i]) j=nxt[j];
nxt[i+]=j+;
}
return;
}
int main()
{
char s[];
while(~scanf("%s",s))
{
int l=strlen(s);int ans=;
int flag=;
getn(l,s);
int maxx=nxt[l];
mem0(vis);
vis[maxx]=;
if(maxx==) puts("Just a legend\n");
else
{
while(maxx>){
vis[maxx]=;
maxx=nxt[maxx];
}
for(int i=;i<l;++i)
{
if(vis[nxt[i]]&&nxt[i]>ans)
ans=nxt[i],flag=;
}
if(!flag) puts("Just a legend\n");
else printf("%s\n",s+l-ans);
}
}
return ;
}