其实就是最大前后缀长度数组~ e.g. abcabc ---->abcabcabc 最少增加3个

多求一位nextArr 可以看出之前4个复用 所以再添一位就好~

总结： 在KMP中nextArr数组基础上 多求一位终止位 将不是的补上即可

package zuoshen1;

public class KMP_ShortestHaveTwice {
public static String answer(String str){
if(str==null) return null;
char[] s=str.toCharArray();
if(str.length()==1)
return str+str;
if(str.length()==2)
return s[0]==s[1]?str+String.valueOf(s[0]):str+str;
int cn=getNext(s);
return str+str.substring(cn);
}
public static int getNext(char[] match){
if(match==null||match.length<2){
return -1;
}
int[] next=new int[match.length+1];//比KMP多一位
next[0]=-1;
next[1]=0;
int cn=0;
int pos=2;
while (pos<match.length){
if(match[pos-1]==match[cn]){
next[pos++]=++cn;
}else if(cn>0){
cn=next[cn];
}else {
next[pos++]=0;
}
}
return next[next.length-1];
}

public static void main(String[] args) {
System.out.println(answer("a"));
System.out.println(answer("aa"));
System.out.println(answer("ab"));
System.out.println(answer("aba"));
System.out.println(answer("abc"));

}
}