建设企业网站企业网上银行,网站托管服务协议,石家庄最好的网站建设公司,做网站4核是什么意思文章目录 题目描述基本思路实现代码 题目描述
给定一个字符串S#xff0c;以及一个模式串P#xff0c;所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现的位置的起始下标。
输入格式
第一行输入整数… 文章目录 题目描述基本思路实现代码 题目描述
给定一个字符串S以及一个模式串P所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N表示字符串P的长度。第二行输入字符串P。第三行输入整数M表示字符串S的长度。第四行输入字符串S。
输出格式
共一行输出所有出现位置的起始下标下标从0开始计数整数之间用空格隔开。
数据范围
1 ≤ N ≤ 10^51 ≤ M ≤ 10^6
基本思路
KMP算法是一个经典的字符串匹配算法。字符串匹配如果使用蛮力算法实现则最坏情况下的时间复杂度是O(m*n)其中m和n分别是母串和子串的长度KMP算法将该时间复杂度优化到了O(mn)可以说实现了一个重大的飞跃。KMP算法可以分为求next数组和基于next数组的字符串匹配两部分其中前一部分会更加困难一些。在字符串匹配部分采用的方法是一种双指针算法两个指针分别指向母串和子串中的一个待匹配字符。每次都比较两个指针所指向的字符如果字符相同发生匹配的情况则同时将指针移动到下一个位置如果字符不同发生失配的情况则进行分情况讨论 对于子串的首字符失配则直接将母串的指针移动到下一个位置对于子串的非首字符失配则根据已经得到的next数组修改子串指针所指向的位置避免从头开始匹配带来的冗余消耗。 next数组的求解是KMP算法最困难的部分下面进行介绍 next数组中的每一个元素的值表示从字符串的首个字符开始到当前元素对应的字符结束所构成的子串的最长相同前后缀的长度。注意这里的最长相同前后缀不包含字符串本身。next数组的首元素需要手动进行初始化设置其值为0。next数组的构建同样是基于双指针算法完成的。起初分别设置两个指针指向字符串的第一个字符和第二个字符之后这两个指针都会向后移动。 当两个指针指向的字符相同时则当前右指针对应的字符的next数组元素值就是在上一个元素的next数组元素值上自增1当两个指针指向的字符不同时则说明当前的最长相同前后缀分别加上左右指针所指向的字符后无法继续构成相同的前后缀因此就需要尝试寻找更短子串构成最长相同前后缀即代码中的prefix_length ne[prefix_length - 1]部分。这一部分理解起来比较复杂因此下面通过一个实例进行介绍。假设需要构建对应的next数组的字符串是ABACABAB且当前已经完成匹配的部分是第一个到第三个字符ABA和第五个到第七个字符ABA第七个字符A对应的next数组值是3。现在左指针指向了第四个字符C右指针指向了第八个字符B显然两者不同因此左右两边的字符串增加了新字符后ABAC和ABAB显然不是相同的前后缀因此我们需要使用别的方式计算由这八个字符构成的字符串的最长相同前后缀。直观上我们发现如果需要构建最长相同前后缀那么就需要两个条件加入的新字符完全相同、加入新字符前的前缀和后缀完全相同。这样就可以产生一个巧妙的构思既然当前字符串的最长相同前后缀分别增加一个新字符后无法继续构成最长相同前后缀那么我们能不能退而求其次不是使用当前的最长相同前后缀而是第二长相同前后缀来构建下一个最长相同前后缀呢这是因为第二长相同的前后缀也满足加入新字符前的前缀和后缀完全相同并且修改了前缀和后缀后前缀的下一个字符也会随着前缀更改一次说不定就可以和右指针新插入的字符相同了。例如对于ABACABA最长的相同前后缀是ABA前三个字符和后三个字符但是最长的相同前后缀再增加第八个字符B后构成的前后缀分别是ABAC和ABAB显然不相同。但是如果使用第二长前后缀A即第一个字符和第七个字符增加一个字符B后仍然可以构成相同前后缀AB。因此在字符串当前的最长相同前后缀无法继续构成下一步的最长相同前后缀时我们可以使用第二长的相同前后缀继续进行尝试如果还不行则使用第三长的相同前后缀…直到找到可以继续构成相同前后缀的相同前后缀或确定不存在可以构成相同前后缀的相同前后缀因为一个字符串的相同前后缀的个数是有限的。现在的问题就是如何找出一个字符串的第二长相同前后缀。对于字符串ABABABA其最长相同前后缀是ABA包含三个字符那么第二长的相同前后缀如果存在则一定只包含两个字符或者一个字符所以我们需要比较该字符串的前两个字符和后两个字符以及第一个字符和最后一个字符。由于我们已经知道了ABA是最长相同前后缀所以后两个字符实际上就是第二个和第三个字符最后一个字符实际上就是第三个字符因此问题就转换为了比较该字符串的前两个字符和第二个第三个字符以及字符串的第一个字符和第三个字符是否相同的问题其实也就是前三个字符构成的字符串ABA的最长相同前后缀问题由于我们求解next数组的过程是顺序进行的因此我们已经计算出了前三个字符ABA对应的next数组元素分别为001因此我们可以得出对于ABA其最长相同前后缀的长度为1因此对于字符串ABABABA其第二长相同前后缀的长度也是1。因此在最长相同前后缀ABA无法继续构成最长相同前后缀时我们使用第二长的相同前后缀尝试继续构建最长相同前后缀构建出了AB成功
实现代码
#include iostream
using namespace std;// 创建一个静态数组ne作为next数组
const int n 1e5 10;
int ne[n];// 获取next数组的函数
// 传入的参数分别是字符串的长度N和字符串P
// 函数根据传入的参数计算next数组
void get_next(int N, const string P)
{// 首先将第一个元素对应的next值设置为0ne[0] 0;// 定义并初始化两个指针int prefix_length 0, j 1;// 通过循环的方式求解next数组直到完成对字符串的遍历while(j N){// 情况1两个指针所指向的字符相同则说明最长相同前后缀可以同时自增并记录结果if(P[prefix_length] P[j]){ prefix_length;ne[j] prefix_length; j;}else{// 情况2两个指针所指向的字符不同且第一个指针并不是指向字符串首字符则根据next数组找出次最长相同前后缀if(prefix_length ! 0) prefix_length ne[prefix_length - 1];// 情况3两个指针所指向的字符不同且第一个指针指向字符串首元素则直接将此处记录为0即可else{ne[j] 0; j;}}}
}// 进行KMP字符串匹配的函数
// 传入的参数分别是子串的长度N、子串P、母串的长度M、母串S
// 函数会在控制台输出子串P在母串S中所有出现位置的首字符下标
void KMP_search(int N, const string P, int M, const string S)
{// 首先根据子串P获取其对应的next数组get_next(N, P);// 定义并初始化母串和子串的指针int pp 0, sp 0;// 通过循环进行字符串匹配当超出母串长度时停止循环while(sp M){// 情况1当前母串和子串的对应字符相同则指针同时自增比较下一个元素if(P[pp] S[sp]) { pp; sp;}else{// 情况2当前母串和子串的对应字符不同且不是发生在子串第一个元素则基于next数组修改子串指针if(pp ! 0) pp ne[pp - 1];// 情况3当前母串和子串的对应字符不同且发生在子串的第一个元素则直接将母串指针自增else sp;}// 每一次当子串遍历完成一次则输出一次出现下标并基于next数组修改子串指针if(pp N){cout sp - pp ;pp ne[pp - 1];}}
}int main(void)
{int N, M;string P, S;cin N P M S;KMP_search(N, P, M, S);return 0;
}
