代码实现如下：
public static int[] getPrefix4(String str){
int[] prefix = new int[str.length()];
int j = 0;
int i = 1;
while(i < str.length()){
if (str.charAt(j) == str.charAt(i)){
// 更新j，同时j 也正是已匹配的最大长度
j ;
prefix[i] = j;
i ;
}else if(j == 0){
// 当str.charAt(j) != str.charAt(i) && j == 0时，后移i即可
i ;
}else{
// 找到已匹配的部分，继续匹配即可
j = prefix[j-1];
}
}
return prefix;
}
2.4 求解next
很多kmp算法的讲解都提到了next数组，那么实际上next数组求解和上面的prefix求解本质是一样的，next[i]实际上就是以i-1为结尾的最长的相同真前后缀的长度。
定义next[j]为当s[i] != p[j]时，需要跳转匹配的模式串的索引，特别的当next[0] = -1
public static int[] getNext(String str){
int[] next = new int[str.length() 1];
int i = 1;
int j = 0;
// next[0] = -1 指代匹配失败，更新文本串索引 1
next[0] = -1;
while(i < str.length()){
if (j == -1 || str.charAt(i) == str.charAt(j)){
i ;
j ;
next[i] = j;
}else{
j = next[j];
}
}
return next;
}
2.5 完整代码
public static int search(String s, String p){
int[] next = getNext(p);
int i = 0, j = 0;
while(i < s.length() && j < p.length()){
if (j == -1 || s.charAt(i) == p.charAt(j)){
i ;
j ;
}else{
j = next[j];
}
if (j == p.length()){
return i - j;
}
}
return -1;
}
2.6 优化next
以上面的next数组为例，当i=5，匹配失败时，应该跳转i=1进行比较，但是我们知道s[5]=s[1]="B"，这样匹配下去也是必定会失败的，基于这一点，还可以简单优化下next数组的求解过程。
public static int[] getNext1(String str){
int[] next = new int[str.length() 1];
int i = 1;
int j = 0;
next[0] = -1;
while(i < str.length()){
if (j == -1 || str.charAt(i) == str.charAt(j)){
i ;
j ;
if (i < str.length() && str.charAt(i) != str.charAt(j)){
next[i] = j;
}else{
// 如果相同，根据next[j]跳转即可
next[i] = next[j];
}
}else{
j = next[j];
}
}
return next;
}
三、其他算法
这一部分，介绍几种其他字符串搜索的算法
3.1 BM1977 年，德克萨斯大学的 Robert S.Boyer 教授和 J StrotherMoore 教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM 算法。BM算法的基本思想是通过后缀匹配获得比前缀匹配更多的信息来实现更快的字符跳转。
通常我们都是从左至右去匹配文本串和模式串的，下面我们从右至左尝试匹配并观察下。文本串中的字符“S”，在模式串中未出现，那么我们是不是可以跳过多余的匹配，不用去考虑模式串从文本串中第1个、第2个、第m个字符进行匹配了。可以直接将模式串向后滑动m个字符进行匹配。
继续观察下面匹配失败的情况，我们可以发现，模式串后三个字符“E”、“L”、“P”一定无法和文本串中的字符“M”进行匹配。换句话说，直到移动到模式串中最右边的“M”(如果存在的话)之前，都是无法匹配成功的。基于这个观察，我们可以直接向后移动模式串，使最右边出现的“M”和文本串中的“M”对齐，再去继续匹配。
总结：1.当出现失配字符时（文本串的字符），如果模式串不存在该字符，则将模式串右移至失配字符的右边。
2.如果模式串中存在该字符，将模式串中该字符在最右边的位置，和文本串的失配字符对齐。
