public static int[] getNext(char[] chars){
if (chars.length == 1){
return new int[]{ -1 };
}
int [] next = new int[chars.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < chars.length){
if ( chars[pos-1] == chars[cn]){
next[pos++] = ++cn;
}else if (cn > 0){
cn = next[cn];
}else {
next[pos++] = 0;
}
}
return next;
}
public static int getIndex(String str1, String str2){
if (str1 == null || str2 == null || str1.length() == 0 ||
str2.length() > str1.length()) return -1;
int i1 = 0;
int i2 = 0;
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
int [] next = getNext(chars2);
while (i1 < str1.length() && i2 < str2.length()){
if (chars1[i1] == chars2[i2]){
i1++;
i2++;
}else if (next[i2] == -1){
i1++;
}else {
i2 = next[i2];
}
}
return i2 == str2.length() ? i1 - i2 : -1;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。