网站推广方式百度云,网站结构怎么优化,百度指数app下载,书签制作手工目录 引言一、算法概念二、题目描述三、思路讲解三、代码实现四、测试 引言
这个KMP算法就是怎么说呢#xff0c;就是不管算法竞赛还是找工作笔试面试#xff0c;都是非常爱问爱考的#xff0c;其实也是因为这个算法比较难懂#xff0c;其实就是很难#xff0c;所以非常个… 目录 引言一、算法概念二、题目描述三、思路讲解三、代码实现四、测试 引言
这个KMP算法就是怎么说呢就是不管算法竞赛还是找工作笔试面试都是非常爱问爱考的其实也是因为这个算法比较难懂其实就是很难所以非常个人的一个思维逻辑吧反正就是用来区分人的我会你不会那么我就比你牛逼所以那就开始吧。
一、算法概念
这个KMP算法就是用来匹配字符串的在一个字符串中是否有另一个字符串的存在如果存在返回原始字符串中的初始下标
二、题目描述
给定一个字符串 S以及一个模式串 P所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。输入格式
第一行输入整数 N表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M表示字符串 S 的长度。
第四行输入字符串 S。输出格式
共一行输出所有出现位置的起始下标下标从 0 开始计数整数之间用空格隔开。数据范围
1≤N≤1051≤M≤106输入样例
3
aba
5
ababa输出样例
0 2三、思路讲解
这个KMP最重要的就是一个next数组先来说一下这个是什么意思吧next [i] 里面存的是在模板串中的以第i号下标为终点和以第1号下标为起点的两个字符串相等的话它们的长度最长为 j 也就是第 i 号位置的最大的后缀和前缀相等的最大长度是j 然后就是匹配算法了如下图如果说在模板串中到第 j 号下标都匹配成功的话原串的第 i 号下标和模板串的第 j1号下标不匹配了那么最暴力的做法就是将模板串往后移动一位再重新一个一个匹配那么KMP的想法是我之前已经匹配了那么些串了那么能不能用一些性质来帮助我更加高效的匹配呢 然后又因为绿色的都是相等的又因为我们有了next数组可以知道当前的模板串往后移动的话可以知道向后移动的最小距离是多少又能够使得从 [1, ne[j] ]的模板串跟从 [i - j 1, i - 1]的字串是相等的 也就是说能使每一次匹配的原串没有浪费都不用再重新匹配
三、代码实现
然后这个KMP的话下标一般是从1开始的
#include iostreamusing namespace std;const int N 100010, M 1000010;int n, m;
char p[N], s[M];
int ne[N];int main()
{cin n p 1 m s 1;//求next数组for(int i 2, j 0; i n; i) //因为ne[1]就是0可以直接从2开始{while(j p[i] ! p[j1]) j ne[j];if(p[i] p[j1]) j;ne[i] j;}for(int i 1, j 0; i m; i){while(j s[i] ! p[j1]) j ne[j];if(s[i] p[j1]) j;if(j n){printf(%d , i - n);j ne[j];}}return 0;
}四、测试
