Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.
A little later they found a string s, carved on a rock below the temple‘s gates. Asterix supposed that that‘s the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring t of the string s.
Prefix supposed that the substring t is the beginning of the string s; Suffix supposed that the substring t should be the end of the string s; and Obelix supposed that t should be located somewhere inside the string s, that is, t is neither its beginning, nor its end.
Asterix chose the substring t so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring t aloud, the temple doors opened.
You know the string s. Find the substring t or determine that such substring does not exist and all that‘s been written above is just a nice legend.
You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.
Print the string t. If a suitable t string does not exist, then print "Just a legend" without the quotes.
fixprefixsuffix
fix
abcdabc
Just a legend
完全没有想法。先开始脑抽了，想了个二分，很激动的认为对了，结果wa，然后发现公共前缀的公共后缀的长度似乎不能二分。。。gg
又学了一下kmp。。。之前学的忘光了。。。
还是不太懂（mark）
这道题巧妙地利用了kmp中的nxt，这里的nxt就是kmp中预处理的失配函数。nxt[i]表示的是[1-i]位置的字符串中最长的前缀和后缀的公共部分的长度(s=abcab的nxt[5]=2,因为s[1-2]=s[4-5])
我们要求的正好和nxt所表示的东西很相似，于是就用上。
求完nxt，把每个长度标记。nxt[n]不标记，因为这是开头和结尾，不能算作中间的最长长度
从nxt[n](n是字符串长度)开始,表示的是整个串的前后缀最长公共部分的长度，如果这个长度存在，那么就可以了。（因为这个是最大的nxt,nxt是递减的）
挖个坑，似乎还是不是很理解
#include<cstdio> #include<cstring> using namespace std; #define N 1000010 int n; int nxt[N],used[N]; char s[N]; void Init() { int j=0; for(int i=2;i<=n;i++) { while(j&&s[i]!=s[j+1]) j=nxt[j]; if(s[i]==s[j+1]) j++; nxt[i]=j; } } int main() { scanf("%s",s+1); n=strlen(s+1); Init(); for(int i=1;i<n;i++) used[nxt[i]]=1; used[0]=0; for(int i=n;i;i=nxt[i]) if(used[nxt[i]]) { for(int j=1;j<=nxt[i];j++) printf("%c",s[j]); return 0; } printf("Just a legend"); return 0; }
原文：http://www.cnblogs.com/19992147orz/p/6284076.html