实现字符串匹配的KMP算法
2024-04-02 15:18:41
KMP算法是Knuth-Morris-Pratt算法的简称，它主要用于解决在一个长字符串S中匹配一个较短字符串s。
首先我们从整体来把我这个算法的思想。
字符串匹配的朴素算法：
我们容易想到朴素算法，即对于目标字符串s和检索对象字符串S，有如下的匹配流程。
while(没有完成匹配)
{
index_S++
temp = index_S
for index_s ,1 to strlen(s)
{
if(s[intdex_s] != S[temp]) break;
else temp++;
}
}
而KMP算法优化朴素算法的精髓，就是在index_S++这一部分。
我们设想，在for中我们正在进行一次匹配，此时已经完成了长度为index_s的匹配，但是在index_s + 1的时候不再满足条件。
首先我们假设长度为index_s的字符串没有字符相同，那么显然，index_S++能够完成index_s次。
其次我们考虑如果已经匹配的index_s的字符串中所有后缀和所有前缀有交集，那么我们如果依然进行上一段的操作会存在漏掉某种匹配情况的危险，因此我们要合理的避免这种危险的发生，即index_S++需要进行index_s - common次，其中common表示已完成匹配的长度index_s的字符串的前缀和后缀的交集中，最长的字符串的长度(有些拗口，需要充分理解)。
这就是KMP的基本思想或者是其正确性的阐述。
最新文章
- mysql5.6-5.7性能调优
- HDU 2871 Memory Control
- js8月-4号，,思想
- Himi的base64代码
- MySQL与Oracle主键Query性能测试结果
- 为Activity设置特定权限才能启动
- Switch Case语句中多个值匹配同一个代码块的写法
- strcpy, mencpy, memmove三者区别
- C#学习日志 day7 --------------LINQ与Lamda语句的初步尝试以及XML的生成
- ABP领域层——仓储（Repositories）
- ESB 设计
- APP性能测试工具
- C#中函数的功能和类型
- 前端工程之CDN部署
- gc实例与gc报告的阅读
- 【Android Studio安装部署系列】三、Android Studio项目目录结构
- Forward团队-爬虫豆瓣top250项目-模块测试
- ADT下载地址(申明：来源于网络)
- dxRatingControl使用
- dp乱写1：状态压缩dp（状压dp）炮兵阵地