网站开发 ip6,松江区做网站,建设银行网站能不能注销卡,网站制作软件有哪些前言
字符串篇#xff0c;继续。 记录 二十五【28.找出字符串中第一个匹配项的下标】 一、题目阅读
给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标#xff08;下标从 0 开始#xff09;。如果 needle 不…前言
字符串篇继续。 记录 二十五【28.找出字符串中第一个匹配项的下标】 一、题目阅读
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。
示例 1
输入haystack sadbutsad, needle sad
输出0
解释sad 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 所以返回 0 。示例 2
输入haystack leetcode, needle leeto
输出-1
解释leeto 没有在 leetcode 中出现所以返回 -1 。提示
1 haystack.length, needle.length 104
haystack 和 needle 仅由小写英文字符组成二、尝试实现
思路一
第一反应遍历haystack如果首字母匹配固定i开启第二层循环看是否全字匹配。应该可以。尝试。 1第一次尝试遇到的问题
class Solution {
public:int strStr(string haystack, string needle) {for(int i 0;i haystack.size();i){if(haystack[i] needle[0]){int k 1;//指针指向needlefor(int j i1;j haystack.size();j){if(k needle.size() haystack[j] ! needle[k]){i j;break; }else if(k needle.size()){return i;}}}}return -1;}
};int k 1找到第一个字母匹配想从第二个字母开始判断。所以j i 1。return i在第二层for循环里面这是默认haystack有2个及以上的字母。如果haystack是单个字母无法进入j的遍历。如下case不成立 haystack aneedle a。这个case无法通过。所以第一次修正。
2第二次尝试修正第一个问题
class Solution {
public:int strStr(string haystack, string needle) {for(int i 0;i haystack.size();i){if(haystack[i] needle[0]){int k 0;//指针指向needlefor(int j i;j haystack.size();j){if(k needle.size() haystack[j] ! needle[k]){ //等式不成立不影响k操作i j;break; }else if(k needle.size()){ //因为判断是否相等时操作k最后k会超出needle的下标所以上面k needle.size()也要判断return i;}}}}return -1;}
};这一遍出现的问题i j以为从i起始往后长度是needle和needle单词不是全字匹配就空掉j个长度。可能是交叉出现的例如下面case haystack mississippineedle issip。错误原因但i 1j 5因为不相等需要break但把i j 跳过正确答案return 4.所以i要一步一步往后走不能跳过。
3再次修正
class Solution {
public:int strStr(string haystack, string needle) {for(int i 0;i haystack.size();i){if(haystack[i] needle[0]){int k 0;//指针指向needlefor(int j i;j haystack.size();j){if(k needle.size() haystack[j] ! needle[k]){break; }else if(k needle.size()){return i;}// k;如果k放到这里if里面的k要取消同时k needle.size()-1。}}}return -1;}
};本次测试通过完成实现。 三、代码随想录学习
学习内容
KMP算法——解决字符串匹配的问题。在“文本串”中找“模式串”。对应题目haystack是“文本串”needle是“模式串”。
1为什么KMP算法找字符串匹配能更快 答 二、中的代码就是暴力实现。i在文本串中一步一步后移第一个if判断haystack[i]和needle[0]比较。所以如果不是全字匹配i后移一位重新和needle[0]比较。总结每轮遇到不相等的字母新开一轮和模式串的初始位置比较。 新开一轮后如果能从模式串中间的某个位置继续比较看起来比重头来过要好。那咋知道遇到不相等字母时从中间的哪个位置开始呢跳到哪个下标可以继续呢答案 前缀表。解释它是一个数组起个名字叫“next”。长度和模式串的长度一样。如果当前位置字母不相等查看前一个位置的前缀表数值跳转到该下标。假设从B位置跳到A位置说明A位置之前的区间不包含A等同于从B位置往前数长度A这个区间看图。 2发现从下标6跳转到下标2下标2前面的区间不包含2c a。和从下标6往前数2个的区间c a一样。 对于“cacbca”前缀和后缀相等的最长长度是2前缀c a。后缀c a不能是a c所以不是对称的意思3原理
位置B跳转到位置A——
A之前的区间不包含A 这段长度为x。B往前数长度x不包含B的区间。下图展示了两段区间以上两个范围内容一模一样也就是包含j-1的区间中前缀和后缀一样。找前缀后缀长度的最大值为了回退最少。
代码实现
前缀表的数值不做任何改动也不去右移/减1再加1。遇到不相等的位置就看前一个元素前缀表数值多少跳转到对应下标。
class Solution {
public:void getNext(int* next,string s){next[0] 0;//第一位没有前缀int j 0;//前缀后缀最长时j指向前缀的末尾。也就是往next里面放的值。for(int i 1;i s.size();i){while(j 0 s[j] ! s[i]){j next[j-1];}if(s[j] s[i]){ //前缀后缀最长时可能中间有重叠。j;}next[i] j;}}int strStr(string haystack, string needle) {int size needle.size();int* next new int[size]{0};getNext(next,needle);//用这个函数来获取前缀表,传进去一个数组用来装值和处理的字符串for(int i 0;i size;i){coutnext[i]\t;}int j 0;for(int i 0;i haystack.size();i){while(j 0 needle[j] ! haystack[i]){j next[j-1];}if(haystack[i] needle[j]){j;}if(j needle.size()){delete[] next;return (i-needle.size()1);}}delete[] next;return -1;}
};1问题为什么求前缀表当i和j不相等时j next[j-1]而不是j一点一点的往前退可以一下跳转到next[j-1] 答细想绿色两段相同并且是最大长度下的相同。 总结
KMP算法解决匹配问题。当遇到不匹配项回退重新比较可以不用从头开始可以在中间的某个位置继续进行。如何确定在哪个位置继续比较用前缀表。前缀表保证从下标B跳转到下标A0~ (A-1)下标范围和(B-A)~(B-1)下标范围内容一样可以不再重复比较。求前缀表的时候初始化——当s[j] ! s[i]时跳转到下标next[j-1]处——当s[j] s[i] 时j前缀增加一位。
欢迎指正转载标明出处
