KMP算法

next数组

经推导发现,进行模式匹配时,子串的移位规律与主串内容无关，与子串的内容有关,
因此根据子串的内容,生成基于子串的next数组，用来存放在对应位置如果发生失配,
应该将子串的哪个位置移动到失配位置
1.失配位置的前缀：永远是子串第一位
2.失配位置的后缀：失配位置的前一位
3.失配位置的前后缀相同位数：
从第一位开始的n位和从后缀开始倒数的n位相同,但前缀连续长度最长不能包含后缀那一位,
后缀也不能包含前缀,重叠也没关系,就说失配位置的前缀和后缀有n位相同
例：
ababc
若在倒数第二位的b位置(位置4)失配，则位置4的前缀是位置1的a,后缀是位置3的a,
从位置1和位置3开始,二者只有一位相同，则前后缀有1为相同,
若在最后一位位置5失配,前缀a虽然和后缀b不相同，但前缀连续两位ab和后缀连续两位ab相同
则c的前后缀有两位相同
ssssb
若在b位置失配,前缀连续sss,后缀连续sss,虽然重叠位置2和位置3的s,但前后缀相同位数为3
4.next数组值
失配位置的next数组值 = 失配位置的前后缀相同位数 + 1
特殊情况:子串位置1的next数组值为0,位置2的next数组值为1
例：

T:	a	b	a	b	a	a	a	b	a
下标:	1	2	3	4	5	6	7	8	9
next:	0	1	1	2	3	4	2	2	3

next数组获取代码实现

i后缀	1	2	。	3	4	5	6	7	。	8	9
j前缀	0	1	0	1	2	3	4	2	1	2	3

var string = "9ababaaaba"; //第一位存放字符串长度
function getnext(T){
  var next=[];
  next[0]=T.length-1;
  var i = 1;## 前缀
  var j = 0;## 后缀
  next[1] = 0;
  while(i<T[0]){
    if(j==0 || T[i] == T[j]){// 子串自己匹配自己
      i++;
      j++;
      next[i]=j;
    }else{
      j = next[j]; // 自己匹配发生失配,则视前缀为子串,后缀为主串,将前缀回溯
    }
  }
  console.log(next);
}
getnext(string);

KMP算法

代码链接