概述
函数刻画
主串位置不变，next值就是模式串(子串)比较后应跳转的位置
不同位置
next[j]函数
next由模式串决定，看模式串当前比较位的前串中前后缀相同的个数来得k-1的值，next[当前位]=k+1
小补充
PM值：也称部分匹配值，每一位字符及其之前的字符所能匹配(前后缀相等的字符个数)的最大值。右移位数=当前比较的字符位置-对应的PM值，当PM=0时，右移位数最大。
next数组：是由每位字符对应的PM值右移一位（低位补-1）得到的结果
next数组的值：即当前所求next[j]数组，它是由所有next数组对应值+1修正得到的结果
一般题目需要求的话，最好倒推求：即求next数组的值——>next数组
代码实现
优化next函数
nextval数组
1.将当前字符与其next值对应的字符进行比较，如果不同，则当前字符的nextval与当前字符的next值保持一致
2.如果当前字符与其next值对应的字符相同，再比较next字符与其对应的next的字符进行比较，如果不同，则当前字符的nextval就与其next值对应字符的nextval值相同；否则如果当前字符的next字符与next字符对应的next的字符相同，当前字符的nextval就与其next值对应字符的next值对应的字符的nextval值相同......依次比较
总之，比较后与谁相同，nextval就与谁对应的next值相同，否则与当前比较字符的next值相同
代码实现
区别
代码整合
//串的应用
#define maxsize 100;
//类型定义
typedef struct {//顺序串=串数组+串长
char ch[maxsize+1];//下标从1开始存串
int length;
}sstring;
sstring s;//顺序串
//串的模式匹配-KMP算法实现
//求next数组：
void getnext(sstring t,int next[]){//通过模式串求得next数组的值
int i=1;//标记当前比较位置
int j=0; //记录跳转位置
next[1]=0;
while(i<t.length){//下标位置合法 ：？？？？为啥不能取等号
if(j==0||t.ch[i]==t.ch[j]){//字符匹配 或 开始匹配(因为next[0]位置是不用的，next数组是从1开始存储)
++i;++j;//比较下一个
next[i]=j;//记录当前next的值
}
else j=next[j];// 失配跳转
}
}
//匹配算法
int KMP(sstring s,sstring t,int next[]){
int i=1;//标记主串位置下标
int j=1;//标记子串位置下标
while(i<=s.length&&j<=t.length){
if(j==0||s.ch[i]==t.ch[j]){//字符匹配或第一个字符就失配，指针下移
++i;++j;
}
else j=next[j];//不匹配时，子串跳转，主串不变
}
if(j>t.length)
return i-t.length;//匹配成功，返回首字符在主串中的下标位置
else return 0;
}
//求nextval数组：与求next数组大致相同，只不过需要内嵌多一次比较
void getnextval(sstring t,int nextval[]){
int i=1;//记录当前位置
int j=0;//记录跳转位置
nextval[1]=0;
while(i<t.length){
if(j==0||t.ch[i]==t.ch[j]){ //字符匹配 或 开始匹配(因为next[0]位置是不用的，next数组是从1开始存储)
++i;++j;//下标后移
//记录当前nextval值
if(t.ch[i]!=t.ch[j]) //后移位置字符不相等
nextval[i]=j;//与next值保持一致
else nextval[i]=nextval[j];//与相同字符的nextval值保持一致
}
else j=nextval[j];//失配跳转
}
}
