Shallow Web

串的模式匹配

April 02, 2020数据结构与算法

介绍

数据结构中的串，类似于线性表。不同之处在于，串的操作一般是多个对多个，不像线性表一个存储单元就是一个独立的数据。

串的匹配

首先我们先了解两个简单的概念：

  • 主串：一个完整的串（如：“abcdef”）
  • 子串：一般是一个完整的串的一部分(如：“abcdef” 中的 “bcde”)，又或者是用于去匹配另一个串的字符串（相对称呼）

朴素匹配算法（暴力匹配）

示例一

比如我们有以下主串与子串

0

匹配步骤如下

demo 1 match

示例二

demo 2 string

匹配步骤

demo 2 match

KMP 匹配算法

示例一

同样，比如我们有以下主串与子串，并且我们由子串计算出了一个 Next 表

demo 1 substr

根据这个表找个下个匹配位置，步骤如下

demo 1 match kmp

示例二

匹配步骤

demo 2 match kmp
jianglin-wu

知命不惧，日日自新。