三：next数组的解释

1.  j是短字符串的指针，i是长字符串；
2. next数组只看短字符串，next[j]=1到j-1的最长前后相等缀+1；
3. 默认next[1]=0;next[2]=1；

如下图：j=4,j前面即j-1到1的子串为aba，最长前后相等缀为a即1，next[4]=1+1=2

               j=6,j前面即j-1到1的子串为abaab，最长前后相等缀为ab即2，next[6]=2+1=3

四：优化

puls优化nextval[j]数组:

        当已经出现过一个字母时，eg：a，则令nextval[3]=next[1]=0

                                                    eg：b，则令nextval[4]=next[2]=1 

        j指针就不用重复遍历已出现的a、b了

这里写的是直接改好的val数组

#include 
using namespace std;#define MAXLEN 225typedef struct
{char ch[MAXLEN];int length;
} String;int  Index_KMP(String S,String T,int next[])
{int i=1,j=1;while(i<=S.length&&j<=T.length){if(j==0||S.ch[i]==T.ch[j]){i++,j++;//匹配成功,i和j向后移动}else{j=next[j];//j回调可以直接匹配的位置}}if(j>T.length) return i-T.length; //不需要+1,因为while1循环退出之前i++,用来while循环判断了else return 0;
}void get_nextval(String T,int nextval[])
{int i=1,j=0;while(i>s1.ch+1;s1.length=strlen(s1.ch)-1;cout<<"输入子串:"<>s2.ch+1;s2.length=strlen(s2.ch)-1;int next[MAXLEN];get_nextval(s2,next);cout<<"nextval数组如下"<