KMP算法

KMP一开始理解起来是比较困难的，下方是结合自己的理解写出来代码，仅作参考，

（网上大部分人处理next数组时，对next数组整体移动了一格。但是我觉得不是特别好理解，所以我写的代码next数组并没有作移动）部分解释请参考注释。

参考代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int next[N];
void getNext(const char *s,int *next)
{/** description:*   构建模式串的前后缀相等的最大长度*   next[i]:存储串s[0...i]前后缀相等的最大长度*   特别考虑s[i] != s[j]:*   现在前后缀不相等，i不移动(除非j回退到0)，*   j需要回退，即缩小前后缀，但是要缩的尽可能小，*   由特殊的“对称性”，j应该回退到 next[j-1]* return: */int len = strlen(s);int i = 1,j = 0;next[0] = 0;while(i < len){if(s[i] == s[j]){next[i++] = ++j;}else{j > 0 ? j=next[j-1] : next[i++]=0;}}
}
int KMP(const char *t,const char *s)
{/** description: t串中找子串s* return: 匹配的第一个子串的首位置（index）*/int i,j;i = j = 0;int lent = strlen(t);int lens = strlen(s);while(i < lent){if(t[i] == s[j]){++i;++j;}else{j > 0 ? j=next[j-1] : i++;}if(j == lens) //如需匹配多个,虚拟模式串s[j]有元素（此时肯定失配）：j = next[j-1]break;}return j == lens ? (i-lens): -1;
}
int main()
{const char *t = "aabcaabaabaaad";const char *s = "aabaabaaa";getNext(s,next);int first_pos = KMP(t,s);cout<<first_pos<<endl;return 0;
}

预处理模式串的理解

用两个“指针”：i, j （i在后，j在前）

初始化：next[0] = 0, i = 1,j = 0
考虑的两种情况：

• s[i] == s[j]: 两个指针均移动（i++，j++）
• s[i] != s[j]: j需要回退尽可能少，j回退到next[j-1],
  需要防止j-1数组越界，当j==0时，即此时j已经无法回退了，只有移动i才可能产生匹配的前后缀。
  (这里堪称KMP算法最难理解的地方)理解不了可以看下图：

入门题目

洛谷：P3375 【模板】KMP字符串匹
AC代码：

#include <iostream>
#include <string>using namespace std;
const int N = 1e6+5;
int pNext[N];
void getNext(string p,int len)
{int j,i;i = 1,j = 0;while(i < len){if(p[i] == p[j]){pNext[i] = ++j;i++;}else{if(j > 0)j = pNext[j-1];elsepNext[i++] = 0;}}
}
void KMP(string s,string p,int lenp)
{int i,j;i = j = 0;int lens = s.length();while(i < lens){if(s[i] == p[j]){i++;j++;}else{if(j > 0) j = pNext[j-1];else i++;}if(j == lenp){int pos = i - lenp + 1;/** 匹配成功后继续匹配：* j从0开始的，j==lenp时，* j已经超出模式串p的范围，* 虚拟模式串s[j]有元素，此时肯定失配，则：j = next[j-1]*/j = pNext[j-1]; cout<<pos<<endl;}}
}
int main()
{string s,p;cin>>s>>p;int lenp = p.length();getNext(p,lenp);KMP(s,p,lenp);cout<<pNext[0];for(int i = 1; i < lenp; ++i){cout<<" "<<pNext[i];}cout<<endl;return 0;
}