相當(dāng)于str1.indexOf(str2)
先求str2每個字符前最長相等的前綴后綴的長度
如敢艰，‘a(chǎn)bcabcd’诬乞，在d字符位置前，前綴與后綴相等的最長長度是3钠导，即abc=abc（前綴后綴不能取整個字符串）震嫉。如，‘a(chǎn)aaaab’牡属，在b字符前票堵，最長長度是4。
求每個字符對應(yīng)的長度逮栅，為next數(shù)組悴势。
如:ababac
| a | b | a | b | a | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 | 1 | 2 | 3 |
如何用？
當(dāng)str2的當(dāng)前字符與str1當(dāng)前字符不匹配時措伐，因為存在前綴后綴相等特纤，可以直接把前綴位置推到str1對應(yīng)的后綴位置，此時前綴和后綴匹配侥加，再往下匹配就行捧存。即str1(i)!=str2(j)時，j=next[j],繼續(xù)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數(shù)組？
數(shù)學(xué)歸納法
next[0] = -1
next[1] = 0
假設(shè)next[i-1] = k
若str2[k]==str2[i-1]
則next[i] = k+1
若不同昔穴，假設(shè)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;
}
