AcWing - KMP字符串(KMP)
发布日期:2021-07-01 00:22:00
浏览次数:3
分类:技术文章
本文共 1085 字,大约阅读时间需要 3 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串M。
输出格式
共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。
数据范围
1≤N≤10^4
1≤M≤10^5输入样例
3
aba 5 ababa
输出样例
0 2
解题思路
题意:求出所有p串在s串出现的位置。
思路:直接利用KMP算法。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 1e4 + 5;const int MAXM = 1e5 + 5;int nex[MAXN];char p[MAXN], s[MAXM];void Get_Next(char str[], int len) { int i = 0, j = -1; nex[0] = -1; while (i < len) { if (~j && str[i] != str[j]) j = nex[j]; else nex[++i] = ++j; }}void KMP(char sa[], int la, char sb[], int lb) { Get_Next(sb, lb); int i = 0, j = 0; while (i < la) { if (~j && sa[i] != sb[j]) j = nex[j]; else i++, j++; if (j >= lb) { j = nex[j]; printf("%d ", i - lb); } }}int main() { int n, m; scanf("%d%s%d%s", &n, p, &m, s); KMP(s, m, p, n); printf("\n"); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99980451 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月28日 18时58分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
顺时针打印矩阵
2019-05-01
从上往下打印二叉树
2019-05-01
二叉搜索树的后序遍历序列
2019-05-01
二叉树中和为某一值的路径
2019-05-01
复杂链表的赋值
2019-05-01
二叉搜索树与双向链表
2019-05-01
字符串的排序
2019-05-01
网络编程
2019-05-01
FOREIGN MySQL 之 多表查询
2019-05-01
MySQL 正则表达式
2019-05-01
IO多路复用
2019-05-01
数据库基本概念
2019-05-01
数据库三范式-详解
2019-05-01
python3之深浅拷贝
2019-05-01
python3之枚举
2019-05-01
异常处理
2019-05-01
python3之编码详解
2019-05-01
python3之end关键字
2019-05-01
python3之文件操作
2019-05-01