炒河粉的无量法师

串的模式匹配

April 02, 2020数据结构与算法

介绍

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

串的匹配

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

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

朴素匹配算法(暴力匹配)

示例一

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

匹配步骤如下

示例二

匹配步骤

KMP 匹配算法

示例一

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

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

示例二

匹配步骤


野生程序猿,专业铲屎官。#Github 账号