【CF126B】password【KMP】解题报告
题目描述：
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.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。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.
题意翻译:
Asterix，Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭，就连Obelix的运气也没好到能打开它。
不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。
Prefix认为T是S的前缀，Suffix认为T是S的后缀，Obelix却认为T应该是S中的某一部分，也就是说，T既不是S的前缀，也不是S的后缀。
Asterix选择子串T来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，Asterix选择了最长的一个（因为Asterix喜欢长的字符串）当Asterix大声读出子串T时，寺庙的大门开了。 （也就是说，你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串）
现在给你字符串S，你需要找到满足上述要求的子串T。
输入格式：
You are given the string ss whose length can vary from 11 to 10^{6}106 (inclusive), consisting of small Latin letters.
一个长度在[1,1000000]间的只包含小写字母的字符串S。
输出格式：
Print the string tt . If a suitable tt string does not exist, then print "Just a legend" without the quotes.
输出子串T，如果T不存在，输出 "Just a legend"，不包含引号。
题解:
首先一看到这道题，要判断字符串是否出现，最先想到kmp,但是单纯用kmp去匹配，是O(N^2)的时间复杂度，但是数据量却有1000000，肯定不行。
那么就得启发我们换换思路，是否一定要匹配呢？
换个角度思考，抛开字符串要在中间出现不谈，既然题目要求最长长度的前后缀，kmp的next数组不就是如此吗？
所以如果next[n]对应的字符串中间出现过，答案肯定就是。那么如何判断呢？如图所示：
如果2~n-1（为何不是1-n,因为题目中说了此串的第三次出现不能在前后缀位置）当中有串和1-next[n]相同，则意味着如果缩短1-i的字符串，把后几位扔掉，总会存在2~n-1的一个i，它的后缀与1~next[n]相同，但是1~next[n]又是1~i的前缀，所以这就是前后缀相同了，只要判断next[i]==next[n]就行了
如果next[n]没有出现过3次，那么1~next[n]的最长相同前后缀一定是答案（因为它长度最大，而且分别在1-next[n]、n-next[n]+1~next[n]出现了2次，总共4次，满足条件)
29行代码搞定
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 char s[1000001],s1[1000001]; 5 int p[1000001],len,p1[1000001]; 6 int main(){ 7 int i; 8 scanf("%s",s+1); 9 n=strlen(s+1); 10 int j=0; 11 for(i=2;i<=n;i++){ 12 while(j&&s[i]!=s[j+1])j=p[j]; 13 if(s[i]==s[j+1])j++; 14 p[i]=j; 15 } 16 int x=p[n],y=n-p[n]+1; 17 for(i=2;i<=n-1;i++)if(p[i]==p[n])len=max(len,p[n]); 18 for(i=y;i<=n;i++)s1[i-y+1]=s[i]; 19 j=0; 20 for(i=2;i<=p[n];i++){ 21 while(j&&s1[i]!=s1[j+1])j=p1[j]; 22 if(s1[i]==s1[j+1])j++; 23 p1[i]=j; 24 } 25 if(p1[p[n]])len=max(len,p1[p[n]]); 26 if(len)for(i=1;i<=len;i++)putchar(s[i]); 27 else puts("Just a legend"); 28 return 0; 29 }
