本文介绍: 给定个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现位置的起始下标

试题传送门:831. KMP字符串 

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

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

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

输入格式

第一行输入整数 N,表示字符串 P 的长度

第二行输入字符串 P。

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

第四行输入字符串 S。

输出格式

一行输出所有出现位置的起始下标(下标从 0 开始计数),整数之间空格隔开。

数据范围

1≤N≤1e5
1≤M≤1e6

输入样例
3
aba
5
ababa
输出样例
0 2

试题解析

题意解释

在一个字符串S中,寻找字串P,输出P在S中对应的下标。

关于KMP算法

首先,介绍一下KMP算法与暴力匹配算法区别

题解代码

最后我们来给出最终的题解代码

#include<iostream>
using namespace std;
constexpr int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int main() {
	int n, m;
	//字符串下标均从1开始
	cin >> n >> p + 1 >> m >> s + 1;

	//j表示匹配成功的长度,i表示p数组中的下标
	//因为p数组下标从1开始,ne[1]一定为0,所以i从2开始
	for (int i = 2, j = 0; i <= n; i++) {
		while (j &amp;&amp; p[i] != p[j + 1]) j = ne[j]; //若不匹配,更新j到ne[j]
		if (p[i] == p[j + 1]) j++; //成功即匹配下一个
		ne[i] = j; //保存next数组
	}
	//j表示匹配成功的长度,从长度为0开始匹配
	for (int i = 1, j = 0; i <= m; i++) {
		while (j &amp;&amp; s[i] != p[j + 1]) j = ne[j]; //若不匹配,更新j到ne[j]
		if (s[i] == p[j + 1]) j++; //成功即匹配下一个
		if (j == n) {
			printf("%d ", i - j); //输出对应下标
			j = ne[j]; //更新j,继续进行匹配
		}
	}
	return 0;
}

 

 

        

 

原文地址:https://blog.csdn.net/m0_73612497/article/details/134723652

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_34722.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注