串的模式匹配
April 02, 2020数据结构与算法
介绍
数据结构中的串,类似于线性表。不同之处在于,串的操作一般是多个对多个,不像线性表一个存储单元就是一个独立的数据。
串的匹配
首先我们先了解两个简单的概念:
- 主串:一个完整的串(如:“abcdef”)
- 子串:一般是一个完整的串的一部分(如:“abcdef” 中的 “bcde”),又或者是用于去匹配另一个串的字符串(相对称呼)
朴素匹配算法(暴力匹配)
示例一
比如我们有以下主串与子串
![0](/static/abd026c352a59c090d68068fe9c5e7e0/fcda8/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-0.png)
匹配步骤如下
![demo 1 match](/static/5e55a3865ba65b67da80e9ca61c7bcf0/fcda8/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-1-match.png)
示例二
![demo 2 string](/static/ce40203956da2836459fe05ff5a39965/d024a/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-2-string.png)
匹配步骤
![demo 2 match](/static/a9fc6140aeb0a78caf535a37e696e3ab/d024a/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-2-match.png)
KMP 匹配算法
示例一
同样,比如我们有以下主串与子串,并且我们由子串计算出了一个 Next 表
![demo 1 substr](/static/c8a631864d4a155e074ad484e7cddad3/30592/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-1-substr.png)
根据这个表找个下个匹配位置,步骤如下
![demo 1 match kmp](/static/4953b5ff1b7b9f64aae1547653503b61/fcda8/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-1-match-kmp.png)
示例二
匹配步骤
![demo 2 match kmp](/static/9ad7b85497da89c78c6a4ccdf7ad8316/d024a/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95-demo-2-match-kmp.png)