导图社区 字符串匹配
字符串匹配算法知识总结,包括BF算法、RK算法、KMP算法、BM算法、Sunday算法等,还有他们的时间复杂度介绍。
社区模板帮助中心,点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
字符串匹配
BF算法
暴力检索法是最好想到的算法,也最好实现,在情况简单的情况下可以直接使用:
时间复杂度:O(MN)
RK算法
RK算法是对BF算法的一个改进
时间复杂度:O(MN)(实际应用中往往较快,期望时间为O(M+N))
KMP算法
用next数组存储当前字符之前的字符串前、后缀最长公共元素长度,匹配失败时通过next数组偏移
时间复杂度:O(n+m)
BM算法
用坏字符表(BS)记录每个字符在模式串中最后的位置,用好后缀表(GS)记录模式串中与后缀匹配的位置,当匹配失败时,取二者中最大的位移量移动
时间复杂度:O(n/m)~O(n+m)
Sunday算法
Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。如果该字符没有在模式串中出现则直接跳过,即移动位数 = 模式串长度 + 1;否则,其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
时间复杂度:O(n)~O(nm)
正则表达式
matlabregexp 匹配正则表达式 regexpi 匹配正则表达式并忽略大小写 regexprep 使用正则表达式替换部分文本 regexptranslate 将文本转换为正则表达式