Gahing's blog Gahing's blog
首页
知识体系
  • 前端基础
  • 应用框架
  • 工程能力
  • 应用基础
  • 专业领域
  • 业务场景
  • 前端晋升 (opens new window)
  • Git
  • 网络基础
  • 算法
  • 数据结构
  • 编程范式
  • 编解码
  • Linux
  • AIGC
  • 其他领域

    • 客户端
    • 服务端
    • 产品设计
软素质
  • 面试经验
  • 人生总结
  • 个人简历
  • 知识卡片
  • 灵感记录
  • 实用技巧
  • 知识科普
  • 友情链接
  • 美食推荐 (opens new window)
  • 收藏夹

    • 优质前端信息源 (opens new window)
关于
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

Gahing / francecil

To be best
首页
知识体系
  • 前端基础
  • 应用框架
  • 工程能力
  • 应用基础
  • 专业领域
  • 业务场景
  • 前端晋升 (opens new window)
  • Git
  • 网络基础
  • 算法
  • 数据结构
  • 编程范式
  • 编解码
  • Linux
  • AIGC
  • 其他领域

    • 客户端
    • 服务端
    • 产品设计
软素质
  • 面试经验
  • 人生总结
  • 个人简历
  • 知识卡片
  • 灵感记录
  • 实用技巧
  • 知识科普
  • 友情链接
  • 美食推荐 (opens new window)
  • 收藏夹

    • 优质前端信息源 (opens new window)
关于
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • AIGC

  • Git

  • Linux

  • 数据协议

  • 数据结构

  • 架构设计

  • 算法

    • 二分查找

    • 动态规划

    • 字符串匹配

      • KMP
        • KMP 介绍
          • KMP完整算法
          • 参考
      • Rabin-Karp
      • Boyer-Moore
      • 字符串匹配算法总结
    • 排序算法

    • 约瑟夫环
  • 编程工具

  • 编程范式

  • 编解码

  • 网络基础

  • 通用技术
  • 算法
  • 字符串匹配
gahing
2020-03-24
目录

KMP专题

# KMP 介绍

朴素算法之所以慢,在于逐个比较发现有字符不相同时,会将搜索串向后移动一位,然后重新逐位比较。

倘若我们能根据源字符串和搜索串匹配的部分字符串信息,将搜索串向后移动一定位置,将加快查找避免很多无效操作。

而这个信息就是:搜索串头部和后面某部分字符串会有重复。

比如,对于源串abcabcabd,搜索串abcabd,我们能在搜索串后面找到与搜索串头部的ab进行匹配。

源串和搜索串在比对到搜索串的 d 字符时出现问题,我们会对搜索串进行移动。

移动位数 = 已匹配的字符数 - 已匹配最后一个字符其对应的部分匹配值

后面会说明如何计算,这里我们拿到第二个b的部分匹配值2,计算得到移动位数为5-2=3

其实就是将搜索串移动到源串的第二个ab位置。

在计算部分匹配值之前,我们先说明下前缀后缀的含义。

"前缀"指除了最后一个字符以外,一个字符串的全部头部组合 "后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度

对于字符串abcabd,按以下分析

  • a 前缀:[] 后缀:[],最长的共有长度为0
  • ab 前缀:[a] 后缀:[b],最长的共有长度为0
  • abc 前缀:[a,ab] 后缀:[bc,c],最长的共有长度为0
  • abca 前缀:[a,ab,abc,] 后缀:[bca,ca,a],共有元素为a,最长的共有长度为1
  • abcab 前缀:[a,ab,abc,abca] 后缀:[bcab,cab,ab],最长的共有长度为2
  • abcabd 前缀:[a,ab,abc,abca,abcab] 后缀:[bcabd,cabd,abd,bd],最长的共有长度为0

可以得到部分匹配表:

a b c a b d
0 0 0 1 2 0 
1
2

获取这个部分匹配表的过程又称为覆盖函数(next函数)。

有这样的递推公式:

对于匹配串pattern的前j个字符,若覆盖函数值overlay(j)为k,即a[0]a[1]...a[k-1]=a[j-k]a[j-k+1]...a[j-1](坐标从0开始),则对于 pattern 的前j+1个字符,有:

  1. pattern[k]==pattern[j]:说明在原来前后缀匹配k个字符的基础上,第k+1个字符也匹配了。显然前j+1个字符的覆盖函数值overlay(j+1)=k+1
  2. pattern[k]!=pattern[j]:在原来前后缀匹配k个字符的基础上,找到这k个字符是否还存在前后缀匹配t个字符(即正好又是pattern前j个字符中的前后缀匹配t个字符,初始t=k),若匹配且第t个字符(从0计数)与pattern[j]相同,则overlay(j+1)=t,否则t=overlay(t-1)然后重复2过程;过程中若t为0说明已无前缀可匹配后缀了,取overlay(j+1)=0

代码如下

function computeOverlay(pattern){
  var overlay = []
  var k = 0
  overlay[0]=0
  for(var i=1;i<pattern.length;i++){
	  k = overlay[i-1]
    if(pattern[k]===pattern[i]){
      overlay[i]=k+1
    } else{
      while(k>0&&pattern[k]!==pattern[i]){
        k = overlay[k-1]
      }
      if(pattern[k]===pattern[i]){
        k=k+1
      }
      overlay[i] = k
    }
  }
  return overlay
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码逻辑上做点小优化:

function computeOverlay(pattern){
  var overlay = []
  var k = 0
  overlay[0]=0
  for(var i=1;i<pattern.length;i++){
	  k = overlay[i-1]
    while(k>0&&pattern[k]!==pattern[i]){
      k = overlay[k-1]
    }
    if(pattern[k]===pattern[i]){
      k=k+1
    }
    overlay[i] = k
  }
  return overlay
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# KMP完整算法

function computeOverlay(pattern){
  var overlay = []
  var k = 0
  overlay[0]=0
  for(var i=1;i<pattern.length;i++){
	  k = overlay[i-1]
    while(k>0&&pattern[k]!==pattern[i]){
      k = overlay[k-1]
    }
    if(pattern[k]===pattern[i]){
      k=k+1
    }
    overlay[i] = k
  }
  return overlay
}
function match(s1,s2){
  var n = s1.length
  var m = s2.length
  if(n<m)return -1
  var overlay = computeOverlay(s2)
  f1:
  for(var i=0;i<n;){
    f2:
    for(var j=0;j<m;j++){
      if(s1[i+j]!==s2[j]){
        if(j>0&&overlay[j-1]>0){
          //可跳跃时,移动位数 = 已匹配的字符数 - 已匹配最后一个字符其对应的部分匹配值
          i+=j-1-overlay[j-1]
        } else{
          i++
        }
        continue f1;
      }
    }
    return i
  }
  return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
computeOverlay("abadabab") // [0,0,1,0,1,2,3,2]
1

# 参考

字符串匹配的KMP算法

Knuth–Morris–Pratt algorithm

编辑 (opens new window)
上次更新: 2024/09/01, 23:56:56
01背包
Rabin-Karp

← 01背包 Rabin-Karp→

最近更新
01
浅谈代码质量与量化指标
08-27
02
快速理解 JS 装饰器
08-26
03
Vue 项目中的 data-v-xxx 是怎么生成的
09-19
更多文章>
Theme by Vdoing | Copyright © 2016-2024 Gahing | 闽ICP备19024221号-1
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式