写在前面：博主是一位普普通通的19届二本大学生，平时最大的爱好就是听听歌，逛逛B站。博主很喜欢的一句话花开堪折直须折，莫待无花空折枝：博主的理解是头一次为人，就应该做自己想做的事，做自己不后悔的事，做自己以后不会留有遗憾的事，做自己觉得有意义的事，不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习，在记录知识的同时获得部分浏览量，得到更多人的认可，满足小小的成就感，同时在写博客的途中结交更多志同道合的朋友，让自己在技术的路上并不孤单。

目录:
1.模式串从下标1开始的next数组求解
        数据结构严蔚敏版
        日常算法题版
2.模式串从下标0开始的next数组求解
        模板1
        模板2
3.模式串与主串的匹配
        数据结构严蔚敏版
        日常算法题版

1.模式串从下标1开始

1.1数据结构严蔚敏版

这个版本是官方标配版，第i个位置的next数组值的意义是：前i-1个字符的最大真公共前后缀的长度加1，加1的目的是下一次主串与模式串失配时模式串要跳到的位置。比如我们一个字符串abab那么它在此处的next数组值为0112;

void get_next(char T[],int next[]) { int i=1; int j=0;  next[1]=0; while(i<T[0])//T[0]为字符串长度 { if(j==0||T[i]==T[j])//T[i]表示后缀的单个字符，T[j]表示前缀的单个字符   {    i++;    j++;    next[i]=j; } else   j=next[j];//若字符不相同那么j值回溯  } } 

1.1日常算法题版

有的时候，模式串需要我们手动的输入，我们可以选择从1开始输入字符串，然后求得此模式串的next数组值(注：kmp代表next数组),这个与严蔚敏版不同的是第i个位置的next数组值是前i个字符的最大真公共前后缀长度，比如字符串abab在此段代码中next数组值为0012

   cin>>str+1;//从数组下标为1开始输入 int len=strlen(str+1); int j=0; for(int i=2;i<=len;i++) { while(j>0&&str[j+1]!=str[i])       j=kmp[j]; if(str[j+1]==str[i])       j++;    kmp[i]=j; } 

2.模式串从下标0开始

2.1模板1

        kmp[0]=0; int j=-1; for(int i=1;i<needle.length();i++) { while(j>-1&&needle[j+1]!=needle[i]) { if(j==0)//j==0的时候陷入死循环 {                     j=-1; break; } else                 j=kmp[j]-1; } if(needle[i]==needle[j+1])                 j++;             kmp[i]=j+1; } 

2.2模板2

        kmp[0] = 0; int t; for(int i = 1; i < s.length(); i++) {       t = kmp[i-1]; while(t > 0 && s[i] != s[t])    t = kmp[t-1]; if(s[i] == s[t]) {     t++;        kmp[i] = t; } else            kmp[i]=0; } 

3.模式串与主串的匹配

3.1数据结构严蔚敏版

int Index_KMP(String S, String T, int pos){ // i 用于主串S当前位置下标值，若pos不为1，则从pos位置开始匹配 int i=pos; //j 用于子串T中当前位置下标值 int j=1; // 定义next数组 int next[255]; // 对串T作分析，得到next数组 get_next(T,next); // 若i小于S的长度且j小于T的长度时，循环继续 while(i<=S[0] && j<=T[0]){ // 两字母相等则继续，相对于朴素算法增加了 // j=0 判断 if(j==0||S[i]==T[j]){ ++i; ++j; } // 指针后退重新开始匹配 else{ // j退回合适的位置，i值不变             j=next[j]; } } if(j>T[0]){ return i-T[0]; } else return 0; } 

3.2算法题版（对应模式串从下标0开始的两个模板）

//haystack表示主串 //needle表示模式串 int i=0;         j=0; int flag; while(i<haystack.length()) {             flag=0; if(haystack[i]==needle[j]) {               i++;               j++;               flag=1; } else { if(j>0) {                 j=kmp[j-1];                 flag=1；               } } if(j==needle.length()) return i-needle.length(); if(flag==0)             i++; } return -1; }