Notes
  • Introduce
  • Go
    • Grammar
      • Basic
      • Goroutines & Channels
      • Test
    • System Library
      • Module
      • sync
      • context
      • net
    • Concurrency in Go
    • The Go Memory Model
    • Code Snippet
  • Rust
    • The Rust Programming Language
    • Rust by Example
  • JAVA
    • Preface
    • Grammar
      • Basic
      • Data Types
      • Operator
      • Exceptions
    • Class Libraries
      • Collection
      • Stream
      • IO
      • NIO
      • RMI
    • Concurrency
      • Preface
      • JMM
      • Synchronized & CAS
      • Deadlock
      • Thread
      • Lock & Condition
      • Utility Class
      • Thread-safe Collection
      • Atomic Class
      • Fork/Join
      • Concurrency Design Patterns
        • Immutable
        • Copy-on-Write
        • ThreadLocal
        • Multitheading If
        • Division
    • JVM
      • Class & Instance Initialization
      • Runtime Data Area
      • Garbage Collection
    • Web Container
      • Tomcat Architecture
      • Jetty Architecture
    • Spring
    • Tuning
      • Programming
  • Computer Science
    • Computer Organization
    • Algorithm
      • Complexity
      • Linear List
      • Sort
      • Binary Search
      • Skip List
      • Hash Table
      • Tree
      • Graph
      • String Matching
      • Bloom Filter
      • Greedy Algorithm
      • Divide and Conquer
      • Back Tracking
      • Dynamic Programming
    • Network Protocol
      • Pysical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer
      • Application layer
      • HTTP
      • HTTP/2 in Action
    • Operating System
      • Basic
      • System Initialization
      • Diagnostic Tools
      • CPU Diagnosis
      • Memory Diagnosis
      • Disk Diagnosis
      • Network Diagnosis
      • Monitor System
    • Design Patterns
      • UML
      • OOP
      • Principle
      • Refactoring & Specification
      • Creational
        • Singleton
        • Factory
        • Builder
        • Prototype
      • Structural
        • Proxy
        • Bridge
        • Decorator
        • Adapter
        • Facade
        • Composite
        • FlyWeight
      • Behavioral
        • Observer
        • Template Method
        • Strategy
        • State
        • Iterator
        • Chain of Responsibility
    • Distributed System
      • Protocol & Algorithm
      • Transcation
      • Theory
      • Resource Management
      • Scheduling
      • Computing
      • Message Queue
      • Cache
      • Consistent Hashing
  • database
    • InfluxDB
      • In-Memory Index
      • Meta
    • MySQL
      • SQL
      • Architecture
      • Log
      • Transaction
      • Indexing
      • Lock
      • Storage
    • Redis
    • Elasticsearch
      • Local Debug
    • HBase
    • Kafka
    • ZooKeeper
  • Reading
    • RocketMQ
    • 演说之禅
    • So Good They Can't Ignore You
    • 学会提问
    • Lecture
  • Other
    • v2ray
    • Kubernetes
    • Git
    • Maven
    • Anaconda And Conda
    • Fuck! Shit!
      • Remove Final by Reflection
      • Ingress Host
      • ExecuterService submit
  • Open source contribution
Powered by GitBook
On this page
  • BF
  • RK
  • BM
  • 坏字符规则
  • 好后缀规则
  • KMP
  • Trie 树
  • 例题
  • AC 自动机

Was this helpful?

  1. Computer Science
  2. Algorithm

String Matching

在字符串 A 中查找字符串 B,A 叫做主串,B 叫做模式串。

BF

Brute Force,暴力匹配算法或朴素匹配算法。

思想:主串长度为 n,模式串长度为 m,在主串中,从起始位置 0、1、2 ... n-m 且长度为 m 的 n - m + 1 个子串中,看有没有和模式串匹配的。

最差时间复杂度 O(n*m),最差情况下,每次需要对比 m 个字符,需要对比 n - m + 1 次。

尽管 BF 算法的时间复杂度很高,但是实际开发中较常用,原因是:

  • 大部分情况下,模式串和主串都不太长。

  • 每次模式串与主串中的子串比较时,中途遇到不能匹配的,就能提前停止,大部分情况不会达到最差时间复杂度。

  • 思想简单,实现简单,不易出错。

RK

Rabin-Karp 算法,由两位发明者命名的。

BF 算法中,每次模式串与主串的子串比较时,都需要比较模式串的每个字符。RK 的核心思路就是计算 n - m + 1 个子串的 hash 值,然后与模式串的 hash 值比较,hash 的比较就非常快了。

但是所有子串计算 hash 值的时候还是要遍历每个子串的所有字符,此时就需要设计一个 hash 算法来优化。

核心思路是 hash 值的计算可以利用前一个子串的计算结果。比如:假设匹配的字符串的字符集只有 K 个字符,可以用 K 进制数来表示一个字符,转换为 10 进制数作为 hash 值。

时间复杂度 O(n)。

如果考虑 hash 冲突,在 hash 值相等后还需要比较原始的字符串。

BM

Boyer-Moore 算法包含两部分,坏字符规则(bad character rule)和好后缀规则(good suffix shift)。

模式串与主串的匹配过程可以看做是模式串不断在主串中往后移动。当遇到不匹配时,BF、RK 算法是模式串往后移动一位;BM 算法的本质就是寻找规则,让模式串尽可能往后多移动几位。

坏字符规则

首先是按照模式串下标从大到小倒着匹配。当发现某个字符(坏字符)无法匹配时,坏字符对应模式串中的下标为 si,然后拿这个坏字符在模式串中从后往前查找,找到下标为 xi,若没有找到 xi = -1,那么模式串就往后移动 si - xi 位。

如下例子,从后往前匹配,c 是坏字符,si = 2,xi = -1,所以模式串往后移动 3 位。移动完成后接着匹配,a 为坏字符,si = 2,xi = 0,所以模式串往后移动 2 位。

a b c a c a b d c
a b d
      a b d
          a b d

最好时间复杂度:O(n/m)。主串:aaabaaabaaab,模式串:aaaa。

问题:主串:aaaaaaaaaaa,模式串:baaa,按照刚才的算法还会后退。

好后缀规则

后缀子串:最后一个字符对齐,如 abc 的后缀子串有 c、bc。 前缀子串:起始字符对齐,如 abs 的前缀子串有 a、ab。

模式串与主串从后往前比较时,在发现坏字符时,前面已经有部分匹配了,匹配的部分叫做好后缀。如下,坏字符为 a,好后缀为 ca。

a b c a c a b d c
    d b c a

原理:模式串已经匹配好的好后缀部分记做 {u},然后好后缀在模式串中继续查找,找另一个与 {u} 匹配的 {u*}:

  • 若能找到 u{*},就将模式串滑动到 {u*} 与主串中好后缀对齐的位置。

  • 若不能找到 u{*},就查看好后缀的后缀子串是否存在与模式串的前缀子串匹配的情况,并找到最长的 {v},然后模式串滑动到 {v} 与主串中 {v} 对齐的部分。

// {u} = de,情况 1 能找到 {u*}
a b c d e f g
d e a d e
      d e a d e

// {u} = de,情况 2 不能找到 {u*},{v} = d
a b c d e f g
e a a d e
        e a a d e

分别计算好后缀和坏字符规则的滑动长度,取最长的滑动。

KMP

KMP 算法与 KM 本质一样,在模式串与主串匹配过程中,若遇到不匹配的,则寻找规律尽量使模式串多往后移动几位。

Trie 树

Trie 树,也叫字典树。专门用于处理字符串匹配的数据结构,解决在一组字符串集合中快速查找某个字符串的问题。

本质:利用字符串之间的公共前缀,将重复的前缀合并在一起。

如下图所示,根节点不包含任何信息,每个节点表示一个字符串中的字符,从根节点到红色节点的路径表示一个字符串。注意:红色节点不一定为叶子节点。

// 假设字符串中只有 a~z 26个小写字母。这种存储方式比较消耗内存。
// 节点可以换成其它数据结构来节约内存,比如跳表、散列表、红黑树等
class TrieNode {
  char data;
  TrieNode children[26];
  public boolean isEndingChar = false;
}

时间复杂度:构建 Trie 树为 O(n),n 表示所有字符串长度总和,构建仅需一次;查找为 O(k),k 为需要查找字符串的长度。

适用条件:

  • 字符集不能太多,不然会消耗很多内存;若节点改成其它数据结构,就会降低效率。

  • 字符串前缀重复较多。

适用场景:

  • 自动不全

  • 搜索关键字提示

与散列表、红黑树比较:精确匹配适合散列表、红黑树等数据结构;前缀匹配适合 Trie 树。

例题

AC 自动机

Aho–Corasick 算法是基于 Trie 树的一种改进算法。

PreviousGraphNextBloom Filter

Last updated 5 years ago

Was this helpful?

LeetCode 208:实现字典树。