当前位置: 首页> 教育> 培训 > 服务商平台官网_dw网站设计步骤_关键词搜索推广排行榜_软文标题

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

时间:2025/7/12 2:28:40来源:https://blog.csdn.net/2301_80221401/article/details/142925098 浏览次数:0次
服务商平台官网_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;
}

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: