当前位置: 首页> 汽车> 时评 > 软件外包个人接单平台_深圳建站公司推荐_seo 优化顾问_阿里云建网站

软件外包个人接单平台_深圳建站公司推荐_seo 优化顾问_阿里云建网站

时间:2025/7/10 21:07:39来源:https://blog.csdn.net/weixin_52630014/article/details/146382231 浏览次数: 1次
软件外包个人接单平台_深圳建站公司推荐_seo 优化顾问_阿里云建网站

1.理解next[]数组的使用与来历

2.求解next[]数组

一、kmp算法的原理

        首先观察暴力解法:假设主串为:abdxxabc,模式串为abxxabd。

暴力解法,就是对主串每个字符作为第一个字符,开始和模式串比较。

比如:从主串第一个字符a开始,比较到d发现不相等,然后从第二个字符b开始,直接不相等。以此类推,直到匹配或者到主串末尾。

           abxabc|abxabd                       ​​​​​​​abxabc|abxabd     ...       abxabc|abxabd

           abxabd                                     abxabd                ...                    abxabd

             图一                                         图二                                       图三

比较操作的时间复杂度为O(m×n)。

kmp算法在此基础上进行改进,关键点为,利用已经比较过的部分,比如图一的abxabd。

        当遇见不匹配的情况时,通过模式串的最长相等前后缀来确定下一次模式串比较的位置,并且不需要回退主串和模式串。前缀为不包含最后一个字符,包含第一个字符的子串,后缀为不包含第一个字符,保护最后一个字符的字串。

        理解:匹配过程中,不匹配的情形只有两种情况,其实也可以看成一种情况。第一种情况:第一个字符就不匹配,也就是说不匹配的字符前面没有字符。如图二。第二种情况:第n个字符不匹配,前n-1个字符匹配。如图一。

       第一种情况由于第一个字符就不匹配,所以主串直接遍历下一个字符,模式串还是第一个字符开始比较。第二种情况:如图一,abxab是匹配的,此时,我们只需要检查abxab这个字符串的最长相等前后缀的长度,最长相等前后缀为ab,长度为2。下一次我们直接比较模式串下标为2的字符x和此时主串不相等的字符c。然后重复上面的比较操作。

        关键点是理解最长相等前后缀的性质。在已经匹配的字符串中,如何最长相等前后缀为0,也即是没有相等的前后缀,那么显然,由于已经匹配的字符串在模式串中为模式串的一个前缀,而在主串中为已经遍历过的匹配的字符串的后缀,假设从i开始比较,到j不相等,主串i ~ j-1这一部分是模式串的一个前缀,因为肯定是从模式串的第一个字符开始比较的。而i - j-1这一部分如果没有相等的前后缀,那么显然不可能有和模式串匹配的部分,因为i~j-1是模式串的一个前缀,你都没有后缀等于前缀,所以主串不用回退,直接遍历下一个字符;如果有相等的前后缀,我们取最长的相等前后缀,i~j-1是模式串的一个前缀,假设最长的相等前后缀长度为2,也就是i, i+1是等于j-2, j-1,所以模式串的下一次比较的位置就是i+2,因为i~j-1也是主串的一部分,主串下一次比较的开始字符是j。

2.关键的最长相等前后缀的求解,也就是常说的next的数组。也就是前缀表。

一、暴力求解:两个指针,left,right,分别指向后缀的开始,前缀的末尾。从最长的前后缀字串开始比较,逐渐缩短,直到不相等。

二、常用解法:kmp的思路,其实求解next数组的过程中也用到了kmp的算法思想。一个指针j,表示以i-1为尾部的前缀字符串的最长相等前后缀的长度,也即是j指向最长相等前缀的下一个字符。i遍历字符串,从0开始。显然,第一个前缀,最长相等前后缀长度为0。

比如字符串abcxabxabcxx。next[]数组:next[0]:前缀a的最长相等前后缀的长度;next[1]:前缀ab的最长相等前后缀的长度;next[2]:前缀abc的最长相等前后缀的长度,....表示以i结尾的前缀字符串的最长相等前后缀的长度。

for(i = 0; i < str.size(); ++i)遍历一个一个求next[i]数组。

if (str[i] == str[j])   next[i] = ++j;

abcxabxabcxx: 假设此时i遍历到了x,j为i-1结尾的前缀字符串的最长相等前后缀长度,也就是红色部分表示的前缀字符串的最长相等前后缀长度,为2,也即是j指向最长相等前缀的下一个字符c。

其实就是next[i]是和next[i-1]有关系的。

关键是str[i] != str[j], while(j > 0 && str[i] != str[j]) j = next[j-1];其实就是把字符串0~j看成模式串,

i-j~i看成主串,因为指针j,表示以i-1为尾部的前缀字符串的最长相等前后缀的长度,也即是j指向最长相等前缀的下一个字符。i-j~i-1是等于0-j-1的。

28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)

参考代码:

class Solution {
public:int strStr(string haystack, string needle) {//第一部分:求解next[]数组vector<int> next(needle.size());int j = 0;for(int i = 1; i < needle.size(); ++i){while(j > 0 && needle[j] != needle[i]){j = next[j - 1];}if(needle[i] == needle[j]){j++;}next[i] = j;}//第二部分:匹配文本串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())return i - j + 1;}return -1;}
};

关键字:软件外包个人接单平台_深圳建站公司推荐_seo 优化顾问_阿里云建网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: