51单片机可以做网站,怎样做好网站用户体验,最大免费发布平台,商丘小程序开发公司有文本串aabaabaaf#xff0c;模式串aabaaf问文本串中是否出现过模式串
暴力解法
最不用动脑子的#xff0c;直接两层for循环#xff0c;逐个匹配#xff0c;匹配到不相等的值时把文本串后移一位#xff0c;再重新比较。这种方法的复杂度是O(mn)#xff0c;该方法低效的…有文本串aabaabaaf模式串aabaaf问文本串中是否出现过模式串
暴力解法
最不用动脑子的直接两层for循环逐个匹配匹配到不相等的值时把文本串后移一位再重新比较。这种方法的复杂度是O(m×n)该方法低效的原因在于重复比较次数过多比如当比较到aabaa时发现此时的f与b不相符又从头开始比较但ff和b前有相同的aa如果我们能直接从b开始比较是不是高效多了呢由此产生了KMP算法。
KMP算法概述
KMP算法就是当模式串与文本串字符不等时不移动至头部进行比较比如f与b不匹配跳至b进行比较节约了前面相同aa的比较次数尝试将比较过程直观展示如下 逐个比较到f发现不匹配
a a b a a b a a f
| | | | | !
a a b a a f此时再从之前已知匹配的aa后面的b开始比较即可
a a b a a b a a f| | | | | |a a b a a f那我们如何得知之前匹配的内容呢这时就要引入前缀表的概念。
前缀表
a a b a a f
0 1 0 1 2 0形如上表这样比较到当前字符发现不匹配时可由前一位对应的字符找到此时应跳转的位置这样的表为前缀表具体如何找到对应字符应跳转的位置要先引入前后缀的概念。 前缀为包含首字母不包含尾字母的所有字串后缀为包含尾字母不包含首字母的所有字串以该模式串为例其所有前缀和后缀为
前缀a aa aab aaba aabaa
后缀f af aaf baaf abaaf模式串不同字串对应的最长相等前后缀表格如下
a aa aab aaba aabaa aabaaf
0 1 0 1 2 0
a a b a a f当不匹配时找前一个字符最长相等前后缀即可在编程中我们将其命名为next数组。
next数组代码示例
a a b a a f
j i
0
void getNext(next,s)//s为模式串{ j0;next[0]0;//初始化ij表示后前缀末尾指向位置for(i1;is.size();i){//后缀指向1第一个字符无后缀故其最长相等前后缀为0while(j0s[i]!s[j])//当前后缀不等时j等于前一个字符对应的next数组位置jnext[j-1];if(s[i]s[j]//前后缀相等时j后移一位i的后移在循环中实现j;next[i]j;}保存next数组}
} 该代码实现了next数组即解决了如果当下不满足时该从何处比较的问题也就是求出不同字符串下最长相等前后缀方式是比较前后缀的最后一位来判定那我想比较前后缀相同不是还要通过两个for循环来实现吗为什么比较前后缀的最后一位就能判定两个不同的字符串最大相等前后缀长度呢 当前后缀相等时我们很好理解因为前面的相等已经判断过了所以如果当下判定位置仍相等时只需在上一次结果上1即可主要是当下判定位置不等时如何理解执行步骤是向前遍历直至找到与后缀字符相等的字符并将前缀末尾指向之想了半天又看了几遍实在不明白咋回事贴两张图看看能不能理解吧好像用到了动态规划的思想
总结
KMP算法是用于比较字符串的一种高效算法特点在于字符串只向前模式串节约了重复部分的比较次数实现通过next数组但涉及next数组的求解人家有很巧妙的办法五行代码就给搞定了比我手算还简单没有明白暂时就到此为止吧。
