字符串匹配

字符串匹配算法知识总结，包括BF算法、RK算法、KMP算法、BM算法、Sunday算法等，还有他们的时间复杂度介绍。

字符串匹配

• 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 将文本转换为正则表达式