KMP
KMP 的思想
kmp的思想就是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去匹配
怎么记录之前已经匹配的内容 ？
一般使用前缀表来做记录
前缀表 ： 记录了模式串 和 文本串 不匹配的时候， 模式串应该从哪里开始重新匹配的信息
案例 （下文所有都会拿这两个举例）： 文本串 : 【 a a b a a b a a f a】 模式串 ： 【 a a b a a f】
有关前缀表
什么是前缀 ?
字符串中前缀是指 不包含最后一个字符的所有以第一个字符开头的连续子字符串
以模式串为例
【a a b a a f】
它的前缀有
[ a ] [ a a ] [ a a b ] [ a a b a] [ a a b a a]
什么是后缀 ?
字符串中后缀是指 不包含第一个字符的所有以最后一个字符结尾的连续子字符串
以模式串为例
【a a b a a f】
它的后缀有
[ f ] [ a f ] [ a a f ] [ b a a f ] [ a b a a f ]
最长相等前后缀
以模式串为例
【a a b a a f】 那么这个的最长相等连续字串就是 0
如果是【a a】 那么它的最长相等连续字串就是 1
如果是【a a b】 那么它的最长相等连续字串就是 0
如果是【a a b a 】 那么它的最长相等连续字串就是 1
如果是【a a b a a】 那么它的最长相等连续字串就是 2
得到前缀表
下标 ：[ 0 1 2 3 4 5 ]
模式串: [ a a b a a f ]
前缀表: [ 0 1 0 1 2 0 ] ——> 我们得到前缀表就是 最长相等前后缀 ，也就是最长相等连续子串
如何利用前缀表找到字符不匹配时指针应该移动的位置
文本串 : 【 a a b a a b a a f a】
下标 ： 【 0 1 2 3 4 5…】
模式串 : 【 a a b a a f 】
前缀表 : 【 0 1 0 1 2 0】
根据不匹配的前一位即前面匹配的那一位的最长相等前后缀的next[i] 的值 和 上面的文本串的下标 进行匹配 ，从而找到指针应该移动的位置
从上面的图中 我们就可以得到 在 文本串的【索引 5】 的地方开始就无法匹配 ， 那么我们要找的就是【索引 4】所对应的前缀表的数值
与之对应的值 为 2 那么我们就从文本串中找到下标为 2 的，从那里开始重新匹配
实现KMP
构造前缀表
代码语言：javascript复制public void getNext(String s , int[] next){
//初始化指针
int j = -1;
next[0] = j;
for(int i = 0; i< s.length();i ){
//前后缀 不相等的情况
while( j >= 0 && s.charAt(i) != s.charAt(j 1)){
j = next[j]; //回退
}
//前后缀 相等的情况
if(s.charAt(i) == s.charAt(j 1)){
j ;
}
next[i] = j; //对前缀表进行赋值 ，赋值最长相等前后缀
}
}
用前缀表来匹配数组
找出文串中 模式串第一个字符的位置（从 0 开始）
答 ： 返回当前在文本串匹配的最后一个位置 i ， 然后再减去模式串的长度 ，就是文本串中模式串的第一个字符的位置
代码语言：javascript复制
// 文本串 模式串
public int strStr(String str , String needle){
if(needle.length() == 0){
return 0;
}
int[] next = new int[needle.length()];
int j = -1 ;
for(int i =0 ; i<str.length;i ){
//不匹配情况
while(j >= 0 && str.charAt(i) != needle.charAt( j - 1)){
j = next[j]; //j 寻找之前匹配好的位置
}
//匹配的情况
if(str.charAt(i) == needle.charAt(j - 1)){
j ;
}
if(j == needle.length() - 1){
return i - needle.length() 1;
}
}
return -1;
}
