算法模板

KMP题目模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的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){j = ne[j];// 匹配成功后的逻辑}
}

模板题

KMP字符串

原题链接

https://www.acwing.com/problem/content/833/

题目

831 . KMP字符串
给定一个字符串 S
，以及一个模式串 P
，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P
在字符串 S
中多次作为子串出现。

求出模式串 P
在字符串 S
中所有出现的位置的起始下标。

输入格式
第一行输入整数 N
，表示字符串 P
的长度。

第二行输入字符串 P
。

第三行输入整数 M
，表示字符串 S
的长度。

第四行输入字符串 S
。

输出格式
共一行，输出所有出现位置的起始下标（下标从 0
开始计数），整数之间用空格隔开。

数据范围
1≤N≤105

1≤M≤106
输入样例：

3
aba
5
ababa

输出样例：

0 2

思路

视频讲解：https://www.acwing.com/video/259/

关于next数组：

“前缀串=后缀串”

题解

#include <iostream>
using namespace std;const int N = 1e5 + 10;
const int M = 1e6 + 10;int n,m;
char p[N],s[M];
int ne[N];int main(){cin>>n>>p+1>>m>>s+1;
//	p为字符数组，cin>>p+1表示字符数组从第二位开始输入！ 即把p[0]空出来，从p[1]开始输入 //	求next数组 for(int i=2,j=0;i<=n;i++){while(j && p[i] != p[j+1]) j = ne[j]; // 在模板串内找前缀串与后缀串相同的位置 if(p[i] == p[j+1]) j++;ne[i] = j;}//	KMP匹配： for(int i=1,j=0;i<=m;i++){while(j && s[i] != p[j+1]) j = ne[j];if(s[i] == p[j+1]) j++;if(j == n){printf("%d ",i-n);j = ne[j];}}return 0; 
}