date: 2016-02-26
categories: Algorithms
tag: [String matching, 字符串匹配]
博客

title: 字符串匹配-Z算法

前言

相比于字符串排序，字符串匹配理解起来就没那么容易了，而且实现其实也比较麻烦。这里我整理下最近学的三个字符串匹配算法。但是如果将三个算法放一篇里无疑是太长了。今天先来看看Z-algorithm。

在Gusfield[1]一书中，Z算法也称为基本预处理（Fundamental pre-processing）。

开篇

首先来定义需要解决的问题以及一些可能接下来常用的表示方式。

字串搜寻算法（String searching algorithms，又译字符串搜索算法）又称字串比对算法（string matching algorithms）是一种搜索算法，是字串算法中的一类，用以试图在一长字符串或文章中，找出其是否包含某一个或多个字符串，以及其位置.[2]

通常使用T来表示待匹配的文本字符串；P表示待匹配的字符；S表示待搜索的字符串。比如：

那么P在T中出现，且出现次数为3，我们输出这三处匹配的位置。

注意S和T虽然在多数情况下是一致的，但不能混淆，在Z算法中S就与T不一样。

虽然中文也能够进行字符串匹配，但是其算法完全不同，这里讨论的是英文字符串的匹配算法。

子串（Substring）

给定一个长度为m的字符串S，我们可以使用$S[i,j]$来表示其所有的子串，其中i与j分别表示其子串的开始和结束的字符位置。所以S也可以表示为：$S[0,m-1]$。

前缀（Prefix）和后缀（Suffix）

为了简化在算法中的描述，我们定义两种特殊的子串，分别是前缀与后缀。

定义：所有形如$S[0,i]$的子串为前缀，其中$i \in (0, m-1)$。同样的所有形如$S[i,m-1]$的子串为前缀，其中$i \in (0, m-1)$

这里我们采用的是较为严格的定义方式，即前缀与后缀非空且不能是字符串。

Z-algorithm

Z值

在正式描述算法原理之前，需要先来定义一个Z算法会使用的特殊值：Z值。

定义: $Z_i$ 是使得从i开始的子串（$S[i,Z_i]$）仍为S ($S[0,m-1]$)的前缀的最大的值.

举例：

注意$Z_i$是由$Z_0$开始的，此时$Z_0 = |S| = 14$ 而在我们对前缀的定义中，前缀不能为字符串本身，所以这种情况忽略。

思路

Z算法的实现分为三步：
1. 定义$S = P \$ T$；
2. 计算S的所有$Z_i$值；
3. 对于所有的i大于P的长度m，如果$Z_i = m$，那么i就是P在T中出现的位置。

步骤1中的$是不出现在T与P中的特殊符号，与任何字符都不匹配。

举例

我们要匹配的T与P如下：

首先我们将组合$P \$ T$形成S字符串，并计算其$Z_i$值，如下：

最后，如果$Z_i = m = 3$，那么 i 就是P在T中出现的位置。

也就是$4$和$7$。

本举例来自于这里

分析

步骤1将两个字符串组合的时间复杂度取决于数据类型，但最多不超过$O(m+n)$，而步骤3仅需遍历一边S，所需时间也是$O(m+n)$，所以Z算法的最终时间复杂度将取决于$Z_i$值计算的时间复杂度。

参考及其他

[1]: D. Gusfield, Algorithms on Strings, Trees, and Sequences:Computer Science and Computational Biology, pp.5-15.
[2]: 字串搜寻算法 - 维基