字符串匹配的算法在很多领域都有重要的应用,这就不多说了。
我们考虑一下算法的基本的描述:给定大小为σ字母表Σ上的长度为n的文本t和长度为m的模式p,找出t中所有的p的出现的地方。
一个长度为m的串p表示为一个数组p[0...m-1],这里m≥0。当然,m=0时,表示空串,用ε表示。p的第i+1个字符用p[i]表示,这里0≤i<m。类似,p[i...j]表示p的子串,第i+1个字符到j+1个字符。0≤i≤j<m。如果i>j,p[i...j]=ε。p[i...j]=p[max(i,0), min(j,m-1)]。
字符串有个连接操作,就是把两个字符串串成一个大的字符串,精确的定义如下:假设u是一个长度为n的字符串,表示为u[0...n-1],v是一个长度为m的字符串,表示为v[0...m-1],u和v的连接uv是一个新的字符串,长度为n+m。设这个新字符串为w,那么有u[0...n-1]=w[0...n-1],v[0...m-1]=w[n...n+m-1]。
事先申明一下,下面提到的词,前缀,后缀,子串,边界,周期等实际上都是字符串,只不过是侧重点不同罢了。
前缀(prefix):如果存在一个词(word) v,满足 uv = w,则称u是w的前缀;
后缀(suffix):如果存在一个词v,满足 uv = w,则称v是w的后缀;
注意到u,v都可能是ε,因此w既是w的前缀,也是w的后缀。
子串(substring)或者因子(factor)如果存在两个词u,v,满足uzv = w,则称z是w的子串或者因子;一个子串u如果既是p的前缀,也是p的后缀,则称为p的边界(border)。
周期(periodic)对于i,0 i <m-p, 有 w[i]=w[i+p],则称p是w的周期,最小的周期记为per(w)。一个词w称为基本的(basic)如果它不能写成另一个词的幂:即不存在词z和整数k满足w=z^k。
一个串p的逆(reverse)记成p,是把p的字母从最后一个开始,到第一个依次连接起来,如果串为p[0...m-1],则它的逆为p[m-1]p[m-2]...p[1]p[0]。
Suff(p)表示串p的前缀的集合。fact(p)为p的因子的集合。
对于文本t和模式p,如果p[0]对齐t[s],p[1]对齐t[s+1],...,p[i]对齐t[s+i],对于i=0,...,m-1,那我们说p在t中位移为s。这时子串t[s...s+m-1]叫做文本的当前窗口。如果t[s...s+m-1]=p,我们说位移s是有效的。那么显然字符串匹配的问题就可以表述为在文本t中找到p的所有有效位移。
大部分的字符串匹配算法工作的方法如下。首先通过一个大小为m的窗口来扫描文本t。对于每个窗口,检查是否与模式p相等(可以通过依次比较窗口和p的每个字符是否相等来判断,或者其他什么方法)。如果窗口和p相同,或者不匹配,那么向右移动窗口到下一个特定位置继续比较。每次比较叫做一次attempt。这种机制通常叫做滑动窗口机制。窗口最初的位置为0(在字符串的最左边),然后向右滑动窗口,直到窗口超出了文本的最右边的边界为止。
一般有三种基本的搜索方法。
前缀搜索:在搜索窗口内从前向后(沿着文本的正向)逐个读入文本字符,查找窗口中的文本和模式串的最长公共前缀,如KMP算法。
后缀搜索:在搜索窗口内从后向前(沿着文本的反向)逐个读入文本字符,查找窗口中的文本和模式串的最长公共后缀,如Boyer-Moore算法。
子串搜索:在搜索窗口内从后向前(沿着文本的反向)逐个读入文本字符,搜索满足如下条件的最长字符串u:u既是窗口文本的后缀,也是模式的子串,如Karp-Rabin算法。