串的模式匹配
April 02, 2020数据结构与算法
介绍
数据结构中的串，类似于线性表。不同之处在于，串的操作一般是多个对多个，不像线性表一个存储单元就是一个独立的数据。
串的匹配
首先我们先了解两个简单的概念：
- 主串：一个完整的串（如：“abcdef”）
- 子串：一般是一个完整的串的一部分(如：“abcdef” 中的 “bcde”)，又或者是用于去匹配另一个串的字符串（相对称呼）
朴素匹配算法（暴力匹配）
示例一
比如我们有以下主串与子串
匹配步骤如下
示例二
匹配步骤
KMP 匹配算法
示例一
同样，比如我们有以下主串与子串，并且我们由子串计算出了一个 Next 表
根据这个表找个下个匹配位置，步骤如下
示例二
匹配步骤
知命不惧，日日自新。