服务商平台官网_dw网站设计步骤_关键词搜索推广排行榜_软文标题

例题：

KMP模式匹配算法

给定目标串s和模式串p，编写程序使用KMP算法进行模式匹配，计算p在s中首次出现的位置，若p不在s中则输出−1。字符串下标从0开始。

输入格式:

输入为2行，第1行为主串s，第2行为模式串p。主串和模式串长度不超过105。

输出格式:

输出为2行，第1行为3个整数，表示分别在模式串p的pm/4​,p2m/4​,p3m/4​处失配后，模式串下一次匹配的位置（即next[j]或f[j−1]+1的值，j=m/4,2m/4,3m/4），每个整数后一个空格，m表示模式串p的长度；第2行为一个整数，表示p在s中首次出现的位置，若p不在s中则输出−1。

输入样例:

qwerababcabcabcabcdaabcabhlk
abcabcabcabc

输出样例:

0 3 6 
6

---

---

 模板：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int ne[N];
char a[N], b[N];
int res;
int main()
{cin >> &a[1] >> &b[1];int n = strlen(a + 1);int m = strlen(b + 1);for (int i = 2, j = 0;i <= m;i++) {while (j > 0 && b[i] != b[j + 1]) {j = ne[j];}if (b[i] == b[j + 1]) {j++;}ne[i] = j;}for (int i = 1, j = 0;i <= n;i++) {while (j > 0 && a[i] != b[j + 1]) {j = ne[j];}if (a[i] == b[j + 1]) {j++;}if (j == m) {res = i - m + 1;j = ne[j];break;}}cout << ne[m / 4] << " " << ne[m / 2] << " " << ne[3 * m / 4] << endl;cout << res-1;
}