KMP算法
一个人能能走的多远不在于他在顺境时能走的多快,而在于他在逆境时多久能找到曾经的自己。
————KMP
板子介绍
两个部分分别实现了next数组的构造
和匹配的过程。
本文均是从下标1开始的。(写题的时候就这么做即可,中间过程无虚任何改动)
最后打印的时候(看样例加和减即可)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010000, M = 10010000; //N为模式串长度,M匹配串长度
char s[N], p[M]; //p是模式,s是被匹配
int n, m;//n是p匹配串大小
int ne[M]; //next[]数组,避免和头文件next冲突
int main()
{
cin >> s+1 >> p+1; //下标从1开始
n=strlen(s+1);//计算大小
m=strlen(p+1);//计算大小
//求next[]数组
for(int i = 2, j = 0; i <= m; i++)
{
while(j && p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
//匹配操作
for(int i = 1, j = 0; i <= n; i++)
{
while(j && s[i] != p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j == m) //满足匹配条件,打印开头下标
{
//如:输出以0开始的匹配子串的首字母下标
printf("%d\n", i - m+1); //(若从1开始,加1)
j = ne[j]; //再次继续匹配
}
}
//打印ne数组,也是从1开始
for(int i=1;i<=m;i++)
{
cout<<ne[i]<<' ';
}
return 0;
}```
标签:匹配,int,next,数组,KMP,strlen
From: https://www.cnblogs.com/yzzyang/p/18145851