深圳网站推广公司,百度学术免费查重入口,宿州品牌网站建设公司,沈阳建设工程信息网下载以后保持每日一更#xff0c;由于兴趣较多#xff0c;更新内容不限于数据结构#xff0c;计算机组成原理#xff0c;数论#xff0c;拓扑学......#xff0c;所谓#xff1a;深度围绕职业发展#xff0c;广度围绕兴趣爱好。往下看今日内容 一.什么是KMP算法 KMP#x…以后保持每日一更由于兴趣较多更新内容不限于数据结构计算机组成原理数论拓扑学......所谓深度围绕职业发展广度围绕兴趣爱好。往下看今日内容 一.什么是KMP算法 KMPKnuth-Morris-Pratt算法是一种字符串匹配算法用于在一个较长的文本串中查找一个模式串的出现位置。
二.KMP算法的应用 这个算法在很多应用中都有重要的作用 字符串搜索KMP算法可以快速在一个长文本中查找一个关键词或者子串的出现位置。因为KMP算法在匹配失败时利用了先前已经匹配过的信息避免了不必要的回溯提高了搜索效率。 文件比较比如两个文本文件的比较KMP算法可以用于找到两个文件中相同的部分或者相似的部分从而进行比较或者合并。 DNA序列匹配在生物信息学中KMP算法可以应用于DNA序列比对和DNA片段的查找这对于基因研究和遗传工程非常重要。 编辑器中的查找和替换很多文本编辑器在实现查找和替换功能时会使用KMP算法用于快速定位和匹配模式串。
三.KMP算法next数组原理(非常重要)
在字符串匹配的KMP算法中求模式串的next数组值的定义如下 问 1当 j1时为什么要取next[1]0 ?
2)为什么要取max{k},k的最大值为多少
3其他情况是什么情况为什么next取next[j]1 解
1当模式串中的第一个字符与主串中的第一个字符不匹配时next[1]0表示模式串应该右移一位主串当前指针往后移动一位再和模式串的第一个字符进行比较。 2当主串的第i个字符与模式串的第j个字符不匹配时主串i不回溯也就是不向前移动则假定模式串的第k个字符与主串的第i个字符比较k值应满足条件1kj并且’p1 p2 ......p(k-1)p(j-k1)p(j-k2)......p(j-1),即k为模式串的下次比较的位置。k的取值可能有多个为了不使右移丢失可能的匹配右移的距离应该取最小由于j-k表示右移的距离所以取max{k}。k的最大值为j-1。
3除了上面两种情况外发生不匹配时主串指针i不回溯在最坏的情况下模式串从第1个字符开始与主串的第i个字符比较。 四.总结
KMP算法与朴素匹配最明显的一个特点就是KMP算法很绝它觉得过去的事情就让它过去不必回头简称“一往无前”。然而朴素匹配算法很委婉很想回头挽留可是最终受伤的总是自己简称“不堪回首”。
可见KMP算法是一个高效率代码简洁逻辑性巧妙的算法。
