【算法基础】KMP字符串
2024-08-26 11:03:14
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串S。
输出格式
共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。
数据范围
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106
个人理解:
很多时候我们会遇到字符串匹配的问题,对于数据量很大的字符串时,我们就需要快一点的算法才能支撑这么大的数据。
我们运用暴力算法,就是两个for循环暴力匹配,但是在暴力的同时会做了很多重复的工作。
for (int i = 0; i < m; i++) {
bool flag = true;
for (int j = 0; j < n; j++)
if (s[i + j] != p[j]) {
flag = false;
break;
}
//...........
}
所以我们需要用算法优化它,前人就已经为我们想好了思路,我们顺着思路理解它就行。(KMP)
我们要简化时间复杂度肯定要从第二个for循环开始优化,我们发现第二个循环存在重复的情况,例如,第一次用第二重循环错了,没循环完成,然后第二次用也是这种情……直到全对,所以想着把中间无用重复的过程给去。
如何省去这些多余的部呢,模板串可不可以直接跳到合适的的下标呢,而不用每次都从头开始匹配呢??
①对模板串进行处理,用数组标记将前缀与后缀相同的部分关联起来。
②与模式串进行比较,不同就移动到模板串所对应的前下标中,依次继续比较。
详细代码:
#include<iostream>
using namespace std; const int N = , M = ;
char p[N], s[M];
int ne[N]; int main() {
int n, m;
cin >> n >> p + >> m >> s + ; //创建一个临时数组,将模板串的前缀与后缀关联起来。
for (int i = , j = ; i <= n; i++) {
//不同了,我们就得将它退到它前面与现在所相同的部分的下标位置。
while (j && p[i] != p[j + ]) j = ne[j];
//相同了共同前进一个位置。
if (p[i] == p[j + ]) j++;
//做好标记。
ne[i] = j;
} for (int i = , j = ; i <= m; i++) {
//模板串所指的位置与模式串不同了,模板串的下标就要移动到上一个与之相同前缀的位置,再次进行比对,直到相等或者下标为零为止。
while (j && s[i] != p[j + ]) j = ne[j];
//如果相同,共同前进一步。
if (s[i] == p[j + ]) j++;
//模板串全部访问完毕,进行输出。
if (j == n) {
cout << i - n << " ";
//回到上一个与之相同的位置。
j = ne[j];
}
} return ;
}
最新文章
- mysql操作查询结果case when then else end用法举例
- c#遍历目录及子目录下某类11型的所有的文件
- Java中的两个关键字——super、this
- 6.3.28微信需群主确认才可进群&;发GIF动图功能内测开始了
- C#:WebBrowser控件设置代理IP访问网站【附源码】
- 2016";百度之星"; - 初赛(Astar Round2A)1002 / HDU 5691 状态压缩DP
- Android 使用Application类保存应用的全局数据
- My集合框架第四弹 HashTable(链表解决冲突)
- 在 Windows系统中编译node.js 源代码
- Repaints and Reflows 重绘和重排版
- VC++:创建,调用Win32动态链接库
- 使用Docker跑MySQL 作为Django的存储后端
- Django1-HTTP协议介绍
- ashx获取Oracle数据库图片
- React---简单实现表单点击提交插入、删除操作
- 一个权重的物体拷贝权重给多个(oneWeightToMany)
- solr简单搜索案例
- 【LOJ#572】Misaka Network 与求和(莫比乌斯反演,杜教筛,min_25筛)
- react 首页加载loading
- curl 详解【转】