题目链接：http://codeforces.com/problemset/problem/126/B
大意：给一个字符串，问最长的既是前缀又是后缀又是中缀（这里指在内部出现）的子串。
我自己的做法是用KMP的next数组，对所有既是前缀又是中缀的位置计数，再从next[n]开始走next，也即枚举所有既是前缀又是后缀的子串，看cnt[i]是否大于0，如果大于0则说明作为中缀出现过（也即有大于i的某个位置的next为i）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int next[N];
int cnt[N];
void getNext(char *word,int n=){
n=(n==)?strlen(word):n;
memset(next,,sizeof(next));
int i,j;
for (i=;i<n;i++){
j=i;
while (j){
j=next[j];
if (word[i]==word[j]){
next[i+]=j+;
break;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
getNext(s,n);
for (int i=;i<n;i++)
cnt[next[i]]++;
if (next[n]==)
puts("Just a legend");
else {
for (int i=next[n];i;i=next[i]) {
if (cnt[i]) {
for (int j=;j<i;j++)
printf("%c",s[j]);
puts("");
return ;
}
}
puts("Just a legend");
}
return ;
}
还有一种枚举方法是扫描所有可能的中缀末位，取next[i]的最大值，也即求出最大的既是前缀又是中缀的子串，再从next[n]开始走next，第一次走到0<next[i]<=len时，也即找到了子串。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int next[N];
void getNext(char *word,int n=){
n=(n==)?strlen(word):n;
memset(next,,sizeof(next));
int i,j;
for (i=;i<n;i++){
j=i;
while (j){
j=next[j];
if (word[i]==word[j]){
next[i+]=j+;
break;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
getNext(s,n);
int len=;
for (int i=;i<n;i++)
len=max(len,next[i]);
for (int i=next[n];i>;i=next[i]) {
if (i>len) continue;
for (int j=;j<i;j++)
printf("%c",s[j]);
puts("");
return ;
}
puts("Just a legend");
return ;
}
第三种方法是用z算法，也就是算出每个位置与本串的最长公共前缀。再枚举所有后缀，check当前后缀是否也是前缀，如果是的话，则看之前是否有z[i]也就是与本串的LCP大于当前后缀长度，如果有，则当前后缀也一定可以作为中缀出现，当前后缀是最长的符合题意的子串。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int z[N];
void Z_match(char *s,int n=) {
n=(n==)?strlen(s):n;
z[]=n;
int l=,r=;
for (int i=;i<n;i++) {
if (i>r) {
l=i,r=i;
while (r<n&&s[r-i]==s[r]) r++;
z[i]=r-l;
r--;
}
else {
int k=i-l;
if (z[k]<r-i+)
z[i]=z[k];
else {
l=i;
while (r<n&&s[r-i]==s[r]) r++;
z[i]=r-l;
r--;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
Z_match(s,n);
int ret=,maxZ=;
for (int i=;i<n;i++) {
if (z[i]==n-i) {
if (maxZ>=n-i) {
ret=n-i;
break;
}
}
maxZ=max(maxZ,z[i]);
}
if (ret==)
puts("Just a legend");
else {
for (int i=;i<ret;i++)
printf("%c",s[i]);
puts("");
}
return ;
}