相当于str1.indexOf(str2)
先求str2每个字符前最长相等的前缀后缀的长度
如，‘abcabcd’，在d字符位置前，前缀与后缀相等的最长长度是3，即abc=abc（前缀后缀不能取整个字符串）。如，‘aaaaab’，在b字符前，最长长度是4。
求每个字符对应的长度，为next数组。
如:ababac
| a | b | a | b | a | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 | 1 | 2 | 3 |
如何用？
当str2的当前字符与str1当前字符不匹配时，因为存在前缀后缀相等，可以直接把前缀位置推到str1对应的后缀位置，此时前缀和后缀匹配，再往下匹配就行。即str1(i)!=str2(j)时，j=next[j],继续if(str1(i)==str2(j)).
public static int getIndexOf(String s, String m){
if(s == null || m == null || m.length() == 0 || s.length() < m.length()){
return -1;
}
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i = 0;
int j = 0;
int[] next = getNextArray(str2);
while(i < str1.length && j < str2.length){
if(str1[i] == str2[j]){
i++;
j++;
} else if(next[j] == -1) {
i++;
} else {
j = next[j];
}
}
return j==str2.length ? i-j : -1;
}
那么如何快速求这个next数组？
数学归纳法
next[0] = -1
next[1] = 0
假设next[i-1] = k
若str2[k]==str2[i-1]
则next[i] = k+1
若不同，假设next[k] = m
比较str2[m]与str2[i-1],相等的话就是str2[i] = m+1,以此类推。
public static int[] getNextArray(char[] str2){
if(str2.length == 1){
return new int[] {-1};
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0; // next[1]
while(i < str2.length){
if(str2[i - 1] == str2[k]){
next[i++] = k + 1;
k++; // next[i]
} else if(k > 0){
k = next[k];
} else{
next[i++] = 0;
}
}
return next;
}
