字符串匹配算法总结草稿

# 前言

之前学过的字符串匹配算法，一种是朴素算法，一种是KMP算法。

朴素算法即暴力，两层for循环，算法复杂度O(n*m)

function match(s1,s2){
  var n = s1.length
  var m = s2.length
  f1:
  for(var i=0;i<n;i++){
    if(s1[i]===s2[0]){
      f2:
      for(var j=1;j<m;j++){
        if(s1[i+j]!==s2[j])continue f1;
      }
      return i
    }
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KMP 的实现比较巧妙，下文会提到，我们先来介绍一种新的算法 Rabin-Karp

最近在分析 adblockplus.js 源码的时候了解到的

此外还有有限自动机算法（Finite Automation）、Boyer-Moore 算法、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法、Shift-Or 算法和 Sunday 算法

# 几种算法的性能比较

编辑

上次更新: 2023/08/23, 09:32:05

← Boyer-Moore 快速排序→