{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAsterix, 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.\u003c/p\u003e\n\u003cp\u003eA little later they found a string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e, carved on a rock below the temple\u0027s gates. Asterix supposed that that\u0027s the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e of the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003ePrefix supposed that the substring \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e is the beginning of the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e; Suffix supposed that the substring \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e should be the end of the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e; and Obelix supposed that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e should be located somewhere inside the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e, that is, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e is neither its beginning, nor its end.\u003c/p\u003e\n\u003cp\u003eAsterix chose the substring \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e 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 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e aloud, the temple doors opened.\u003c/p\u003e\n\u003cp\u003eYou know the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e. Find the substring \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e or determine that such substring does not exist and all that\u0027s been written above is just a nice legend.\u003c/p\u003e"}},{"title":"翻译","value":{"format":"HTML","content":"Asterix,Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭,就连Obelix的运气也没好到能打开它。\u003cp\u003e\n\n不久他们发现了一个字符串S(|S|\u003c\u003d1000000),刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码,于是就大声将字符串朗读了出来,然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。\u003cp\u003e\n\nPrefix认为T是S的前缀,Suffix认为T是S的后缀,Obelix却认为T应该是S中的某一部分,也就是说,T既不是S的前缀,也不是S的后缀。\u003cp\u003e\n\nAsterix选择子串T来满足所有伙伴们的想法。同时,在所有可以被接受的子串变形中,Asterix选择了最长的一个(因为Asterix喜欢长的字符串)当Asterix大声读出子串T时,寺庙的大门开了。 (也就是说,你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串)\u003cp\u003e\n\n现在给你字符串S,你需要找到满足上述要求的子串T。\u003cp\u003e\n\n输入格式:\u003cP\u003e\n\n一个长度在[1,1000000]间的只包含小写字母的字符串S。\u003cp\u003e\n\n输出格式:\u003cp\u003e\n\n输出子串T,如果T不存在,输出 \"Just a legend\",不包含引号。\u003cp\u003e\n感谢@Chemist 提供的翻译"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eYou are given the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e whose length can vary from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e (inclusive), consisting of small Latin letters.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. If a suitable \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e string does not exist, then print \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eJust a legend\u003c/span\u003e\" without the quotes.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003efixprefixsuffix\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003efix\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eabcdabc\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eJust a legend\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"提供一个kmp的模板","value":{"format":"HTML","content":"void getnext(string \u0026s, int *nex, int len){ \u003cp\u003e\n// s的开头是空格 \u003cp\u003e\n int j \u003d 0; \u003cP\u003e\n for(int i \u003d 2; i \u003c\u003d len; i ++){\u003cp\u003e\n \u0026ensp;\u0026ensp;while(j \u003e 0 \u0026\u0026 s[i] !\u003d s[j + 1]){\u003cp\u003e\n \u0026ensp;\u0026ensp;j \u003d nex[j]; \u003cP\u003e\n }\u003cp\u003e\n if(s[i] \u003d\u003d s[j + 1]){ \u003cp\u003e\n \u0026ensp;\u0026ensp;j ++; \u003cp\u003e\n }\u003cp\u003e\n nex[i] \u003d j; \u003cp\u003e\n \u0026ensp; }\u003cp\u003e\n}"}}]}