KMP作为一个广为人知的字符串匹配算法——也是本文的前一半。
旨在讲解next数组的求法，并使读者理解。
#include<iostream> #include<cstring> using namespace std; const int N=5000002; int next[N]; string s1,s2; void init(string s){ for(int i=0,j=next[0]=-1,len=s.size();i<len;){ if(j==-1||s[i]==s[j]) next[++i]=++j; else j=next[j]; } } int main(){ cin >> s1 >> s2; init(s2); for(int i=0,j=0,len=s1.size();i<len;){ if(j==-1||s1[i]==s2[j]) ++i,++j; else j=next[j]; if(j==s2.size())cout << i-s2.size()+1 << endl; }for(int i=1,len=s2.size();i<=len;++i) cout << next[i] << " "; return 0; }
我们先看到 init 初始化函数。
void init(string s){ for(int i=0,j=next[0]=-1,len=s.size();i<len;){ if(j==-1||s[i]==s[j]) next[++i]=++j; else j=next[j]; } }
当然写成while的也行
首先，next[i]数组指的是s字符串中0~i部分的最长的真前缀等于真后缀的长度。
有点绕。
真前/后缀 ： 即不包括原字符串的前/后缀。
比如 ABCAB 的真前缀有 A 、AB 、 ABC 、 ABCA
真后缀有 B 、AB 、 CAB 、 BCAB
因为在匹配过程中如果发现有
i,j表示当前处理的区间是0~i,判断的前缀和后缀长度为j，即前缀0~j-1，后缀 i-j+1~i
其实处理过程就是自己匹配自己。
原文：https://www.cnblogs.com/lsy263/p/11516623.html