KMP算法

判断字符串str1是否含有子串str2

关键是实现next数组

next数组就是针对str2串中每个字符前的子串中存在的前缀与后缀匹配的最长长度

• "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

• 假设str2为“abababca”。

  • j=0，字符str2[j]=a，a前没有字符串，默认为next[0]=-1;

  • j=1，字符str2[j]=b，b前子串为“a”，前后缀不存在，默认为next[1]=0;

  • j=2，字符str2[j]=a，a前子串为“ab”，前后缀不存在相等，则next[2]=0;

  • j=3，字符str2[j]=b，b前子串为“aba”，前后缀最大相等为a，则next[3]=1;

  • 以此类推next[9]=[-1,0,0,1,2,3,4,0]