75%，subString超出
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int max=0;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader =new BufferedReader(new InputStreamReader(System.in));
String string=bufferedReader.readLine();
int[] arrayPatternNext=new int[string.length()];
arrayPatternNext=buildedString(string, arrayPatternNext);
int len=string.length();
if (max==0||max==len-1) {
System.out.println("Just a legend");
}else {
String targetString=string.substring(0,max);//待正确的字符串
string=string.substring(max,len-max);//去除前后缀剩余的字符串, 超出why
if (string.length()<targetString.length()){
System.out.println("Just a legend");
}else {
if (getCommonString(string,targetString,arrayPatternNext)){
System.out.println(targetString);
}else {
System.out.println("Just a legend");
}
}
}
}
private static boolean getCommonString(String a, String patternString, int[] arrayPatternNext) {
int i=0;int j=0;
while (i<a.length()){// 主串的下标一直往前走，则时间复杂度为线性
if (a.charAt(i)==patternString.charAt(j)){
i+=1;j+=1;
}else if (j>0){//因为当前面不匹配的时候，这个匹配串的下标就需要根据next数组作出调整
j=arrayPatternNext[j-1];
}else i+=1; //不相等，字串下标也没有动，主串下标就往前走
if (j==patternString.length()-1){
return true;
}
}
return false;
}
// todo 构建next数组
private static int[] buildedString(String patternString,int[] arrayPatternNext) {
int prefix_len=0;// 共同前缀
int i=1;
char[] chars=patternString.toCharArray();
while (i<patternString.length()){
if (chars[prefix_len]==chars[i]){
prefix_len+=1;
arrayPatternNext[i]=prefix_len;
i+=1;
}else {
if (prefix_len==0){//没有公共前缀
arrayPatternNext[i]=0;
i+=1;
}else prefix_len=arrayPatternNext[prefix_len-1];
}
}
max=arrayPatternNext[arrayPatternNext.length-1];
return arrayPatternNext;
}
}
