文章链接
考点
算法-字符串算法-字符串算法
面5笔5给定一个字符串，如何加最短的字符（只能在原始串的后面进行添加）使其构成一个长的字符串且包含两个原始字符串。
前往“校招VIP”小程序，刷题更快
最新校招难题刷题，快来进刷题群吧
解答
其实就是最大前后缀长度数组~ 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"));
}
}