kmp字符串
2022/8/17 6:22:45
本文主要是介绍kmp字符串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P
在字符串 S中多次作为子串出现。
求出模式串 P
在字符串 S中所有出现的位置的起始下标。
输入格式
第一行输入整数 N
,表示字符串 P的长度。
第二行输入字符串 P
。
第三行输入整数 M
,表示字符串 S的长度。
第四行输入字符串 S
。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0
开始计数),整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例:
3 aba 5 ababa
输出样例:
0 2
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 1e6 + 10; int n, m, ne[N]; char p[N], s[M]; int main()// kmp算法由于j每次最多加1,每次向后最少递归1次,故j最多加n次,最多被弹出n次,由此可得时间复杂度为O(n) { scanf("%d%s%d%s", &n, p + 1, &m, s + 1); // 通过+1使得字符串从下表为1的位置开始读入 for(int i = 2, j = 0; i <= n; i ++ ) // 显然,当i = 1时ne[j] = 0,因为此时只有一个字母,无法自比较 { while(j && p[j + 1] != p[i]) j = ne[j]; // 我们默认j和i-1可以匹配,故当j+1和i无法匹配时,我们就递归的去寻找能匹配的位置 if(p[j + 1] == p[i]) j ++ ;// 显然i位置最多匹配一个j ne[i] = j;// 记录当前位置最大向前匹配到的位置 } for(int i = 1, j = 0; i <= m; i ++ )// 显然,当两字符串进行比较时,要从头开始比较,故i = 1 { while(j && p[j + 1] != s[i]) j = ne[j];// 同理,我们递归的去寻找有可能满足当前位置匹配的最大长度 if(p[j + 1] == s[i]) j ++ ;// 当可以匹配时,我们将j加1 if(j == n)// 当完全匹配时 { printf("%d ", i - j);// 记录答案 j = ne[j];// 递归,继续进行匹配 } } puts(""); return 0; }
这篇关于kmp字符串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署