转载：https://blog.csdn.net/zichen_ziqi/article/details/80848995#
next数组值的解法：
（1）求模式串中，前缀后缀最大的相同长度
A D A B C A D A D A
0 0 1 0 0 1 2 3 2 3
（2）将前缀数组后移一位，并将第一位，置-1
-1 0 0 1 0 0 1 2 3 2
（3）将移位后的数组整体+1
0 1 1 2 1 1 2 3 4 3
求nextval：
转载：https://zhidao.baidu.com/question/1824245523499245828.html
模式串 a b a a b c a cnext值 0 1 1 2 2 3 1 2nextval值 0 1 0 2 1 3 0 21.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。即设第a位next是b，就和第b位比较：
不同，则为本身的next值；
相同，则进一步将b与（b的next值为c）第c位的next值比较。
函数
# include <iostream>
# include <string>
string::size_type position;
position = str.find("listen"); / / 第一次出现的位置
position = str.rfind(flag); / /最后一次出现的位置
KMP：转载：https://blog.csdn.net/v_july_v/article/details/7041827
下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。 很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
代码转载：https://blog.csdn.net/qq_38701476/article/details/81512525
#include<bits/stdc++.h>
bool SUBMIT = false;using namespace std;const int inf = 1000;int nex[inf];string s,h;void Getnex(string m)//对kmp数组的构造{ nex[0]=-1; int k=-1,j=0; while(j<m.size()) { if(k==-1||m[k]==m[j]) { k++;j++; nex[j]=k; }else k=nex[k]; }}int kmp()//用kmp进行匹配{ int k=0,j=0; while(j<h.size()) { if(k==-1||s[k]==h[j]) { k++;j++; }else{ k=nex[k]; cout<<k<<" "<<j<<endl; } if(k == s.size()) return j-k; } return -1;}int main(){ if(SUBMIT)freopen("i.txt","r",stdin);else _; cin>>h>>s; cout<<h<<endl<<s<<endl; Getnex(s); for(int i=0;i<s.size();i++) cout<<nex[i]; cout<<endl; int ans=kmp(); cout<<ans<<endl;return 0;
}