主要是文本串和模式串之间的匹配，来加速匹配的算法。
即在线性时间内求出文本串T中查找字符串P，且求出P在T中出现的次数和位置。
主要是枚举文本串T的每个起始位置i， 然后逐步和字符串P进行比较，如果中途失配，那么i++， 在重新与P进行匹配;
// https://blog.csdn.net/v_july_v/article/details/7041827
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}
else
{
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
Brute Force算法需要的时间复杂度为\(O(mn), m、n分别是T和P的字符串长度\)。
KMP算法可在\(O(m + n)\)时间内完成上述工作。
我觉得KMP算法讲的比较好的是，邓俊辉老师的数据结构课。
https://www.bilibili.com/video/BV1jt4y117KR?p=401
多的也不说，直接开撸。
这里定义的next数组，next[i]表示是除当前字符外的最长相同前缀后缀长度。其实际对应着如果失配，下次需要移动的距离信息(i - next[i])。
特别地，当不存在这样的i时，令next[i] = -1，作为万能哨兵; 其在这里的意义是为了处理当首位置就发生失配的情况，这个时候应该往右移动一个单位。这里不妨假想在P[0]的左侧"附加"P[-1]，且该字符与任何字符都匹配，这点和"next[0] = -1"。
//KMP 匹配主算法
//该算法至多一次完全匹配，如果需要统计出现多次，需要将稍微更改模板;
int match(char* P, char* T)
{
int* next = buildNext(P); //构建next数组;
int n = (int)strlen(T), i = 0; //文本串T的指针;
int m = (int)strlen(P), j = 0; //模式串P的指针;
while (j < m && i < n) {
//匹配，或者P已经移出最左侧;(顺序不可交换)
if (0 > j || T[i] == P[j]) {
i++; j++;
} else {
j = next[j]; //当失配时，模式串右移;
}
}
delete[] next;
return i - j;
}
多次统计模板:
int match(char* P, char* T)
{
int* next = buildNext(P); //构建next数组;
int n = (int)strlen(T), i = 0; //文本串T的指针;
int m = (int)strlen(P), j = 0; //模式串P的指针;
int ans = 0; //统计出现次数;
while ( i < n) {
//匹配，或者P已经移出最左侧;(顺序不可交换)
if (0 > j || T[i] == P[j]) {
i++; j++;
} else {
j = next[j]; //当失配时，模式串右移;
}
if (j == m) {
//这里应该是
//回退一下,因为这个还需要在比较;
i--, j--;
j = next[j];
ans++;
}
}
delete[] next;
return i - j;
}
int* buildNext(char* P)
{
int m = (int)strlen(P);
int j = 0;
int* N = new int[m]; //next表;
int t = N[0] = -1;
//为啥这里是m-1，因为是先++，如果是m的话，继续匹配到m-1时
//会继续执行，这时经过++, 会变为m,这时就会发生数组越界;
//在OJ中经常会开辟多余的buffer，所以表现也能正常工作;
while (j < m - 1) {
if (t < 0 || P[j] == P[t]) { //匹配;
j++; t++;
N[j] = t;
} else { //失配;
t = N[t];
}
}
return N;
}
//比如，这个帖子中的解答;
https://cloud.tencent.com/developer/article/1525236
平时还是需要注意边界，哪怕多一个少一个也不行;
- 初始化 next[1] = 0, 假设 next[1, i - 1]已经求出，下面求解next[i];
- 不断尝试扩展匹配长度j，如果扩展失败(下一个字符不相等时)，令j变为next[j],直到j变为0(应该从头开始匹配);
- 如果能扩展成功，匹配长度j增加1.next[i]的值就是j;
next[1] = 0; //首个位置匹配;
for (int i = 2, j = 0; i <= n; i++) {
//失配时;
while (j > 0 && a[i] != a[j + 1] ) {
j = next[j];
}
//此时要么 j == 0,要么a[i] == a[j + 1];
//如果a[i] == a[j + 1],那么说明可以匹配，则累加;
if (a[i] == a[j + 1]) {
j++;
}
//当j == 0，说明已经失配，此时需要从头开始匹配;
//亦或者之前匹配增加的，记录下来;
next[i] = j;
}
因为这个模板给的是[1, n]上的序列,很容易就可以得到一般程序意义上的[0, n)的模板:
next[0] = 0;
int i = 1, j = 0;
int m = a.size();
while (i < m) {
while (j > 0 && a[i] != a[j + 1]) {
j = next[j];
}
if (a[i] == a[j + 1]) {
j++;
}
next[i++] = j;
}
因为和找next数组类似，所以求解方法很相似:
for (int i = 1, j = 0; i <= m; i++) {
while (j > 0 && (j == n || b[i] != a[j + 1])) {
j = next[j];
}
if (b[i] == a[j + 1]) {
j++;
}
f[i] = j;
//if (f[i] == n) 这里就是A在B中的某一次出现;
}
改进版:
//f[i]是字符串B中以i结尾的字符串，能够和字符串A的前缀能够匹配的最长长度;
//B是文本串，A是模式串;
for (int i = 0, j = 0; i < m; i++) {
while (j > 0 && (j == n || b[i] != a[j + 1])) {
j = next[j];
}
if (b[i] == a[j + 1]) {
j++;
}
f[i] = j;
// //if (f[i] == n) 这里就是A在B中的某一次出现;
}
int i = 0, j = 0;
while (i < m) {
while (j > 0 && (j == n || b[i] != a[j + 1] ) {
j = next[j];
}
if (b[i] == a[j + 1]) {
j++;
}
f[i++] = j;
}
先说个板子题:
HDU1686:
//https://blog.csdn.net/qq_40924940/article/details/83964199
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e6 +50;
int nex[maxn];
char c1[maxn],c2[maxn];
void getnex()
{
int len = strlen(c1);
nex[0]=-1;
int j=0;
int k=-1;
while(j<len-1)
{
if(k==-1||c1[k]==c1[j])
nex[++j]=++k;
else
k=nex[k];
}
}
int k;
int kmp()
{
int i=0,j=0;
int k=0;
int l1 = strlen(c1);
int l2 = strlen(c2);
getnex();
while(i<l2)
{
if(j == -1 || c2[i]==c1[j])
{
i++;
j++;
}
else
j = nex[j];
if(j == l1)
{
k++;
i--,j--;
j=nex[j];
}
}
return k;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",c1,c2);
printf("%d\n",kmp());
}
return 0;
}
至此，普通KMP总结完毕，对于一般的OI/ACM基本已经够用。其实可以有优化的KMP及BM算法，以及效果更好Sunday算法。但是先把题刷起来。
原文：https://www.cnblogs.com/zhanghanLeo/p/14100554.html