AcWing - KMP字符串(KMP)
发布日期:2021-07-01 00:22:00
浏览次数:4
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月29日 22时40分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Go语言并发组件
2019-05-01
Go语言的并发模式
2019-05-01
Linux中如何优雅的删除被打开的文件
2019-05-01
从零开始学Linux内核-----从Unix到Linux
2019-05-01
Linux内核学习----进程管理
2019-05-01
linux内核学习-----进程调度
2019-05-01
算法实现----二分查找go语言实现
2019-05-01
Redis中面试常见的问题整理
2019-05-01
Linux学习---中断和中断处理
2019-05-01
YUV / RGB 格式及快速转换算法
2019-05-01
共享收集的图像处理方面的一些资源和网站
2019-05-01
图像基本知识
2019-05-01
CMarkup
2019-05-01
网络爬虫(蜘蛛)Scrapy,Python安装!
2019-05-01
38款 流媒体服务器开源软件
2019-05-01
Using GDB in Visual Studio
2019-05-01
网络时间协议简介-----NTP(Network Time Protocol)
2019-05-01
简析STUN协议
2019-05-01
Winsock服务器内存资源管理
2019-05-01
Winsock 完成端口模型简介
2019-05-01