串

发表于 分类于

串或字符串属于线性结构，但字符串作为数据结构，结构简单，规模庞大，元素重复率高。所谓结构简单，是指字符表本身的规模不大，甚至可能极小。以生物信息序列为例，参与蛋白质合成的氨基酸只有20种，而构成DNA序列仅有4种。因此，以字符串形式表示的海量文本处理技术，一直都是相关领域的研究重点。

一般地，由$n$个字符组成构成的串记作：

$S=a_0a_1a_2…a_{n-1}$,其中$a_i \in \sum,0\leq i <n$

这里的$\sum$是所有可用字符的集合，称作字符表，例如二进制比特集，ASCII字符集。字符串S中所含字符的总数$n$，称作S的长度，记作$|S|=n$。这里只考虑长度有限的串，特别地，长度为零的串称作空串。

字符串中任一连续的片段，称作其子串。具体地，对于任意$0\leq i<i+k<n$,由字符串S中起始于位置i的长度为k的子串称作后缀，分别记作：

$S.substr(i,k)=a_ia_{i+1}…a_{ i+k}=S[i,i+k)$

特殊地，起始于位置0、长度为k的子串称作前缀，而终止于位置n-1、长度为k的子串称为后缀，分别记作：

$prefix(S,k)=S.substr(0,k)=S[0,k)$

$Suffix(S,k)=S.substr(n-k,k)=S[n-k,n)$

由以上定义可知：空串是任何字符串的子串，也是任何字符串的前缀和后缀。任何字符串都是自己的子串，也是自己的前缀和后缀。

最后，字符串$S[0,n)$和$T[0,m)$相等，当且仅当二者长度相等$(n=m)$,且对应的字符相同(对任意$0\leq i<n$都有$S[i]=T[i]$)。

具体应用

在涉及字符串的众多实际应用中，模式匹配是最常使用的一项基本操作。比如UNIX Shell的grep工具和DOS的find命令基本功能都是在指定的字符串中查找特定模式的字符串。生物信息处理领域，也经常需要在蛋白质序列中寻找特定的氨基酸模式。

以上所有应用问题，本质上都可描述为如下形式：

如何在字符串数据中，检测和提取以字符串为形式给出的某一局部特征。

这类操作都属于串模式匹配范畴，简称串匹配。一般地，即

对于基于同一字符表的任何文本串$T(|T|=n)$和模式串$(|P|=m)$：

  • 判定$T$中是否存在某一子串与$T$相同
  • 若存在(匹配)，则报告该子串在$T$中的起始位置

串的长度$n$和$m$都很大，但相对而言$m$更大，即满足$2<<m<<n$ 。

根据具体应用需求的不同，串匹配模式可以多种形式呈现。

有些场合属于模式检测问题：只关心是否存在匹配而不关心具体的匹配位置，比如垃圾邮件的检测。有些场合属于模式定位问题，若经判断的确存在匹配，则还需确定具体的匹配位置，比如带病毒程序的鉴别和修复。有些场合属于模式计数问题：若存在多处匹配，则统计出匹配的子串总数，比如网络热门词汇榜的更新。有些场合则属于模式枚举问题，若存在多处匹配时，报告出所有匹配的具体位置。

如何对任一串匹配算法进行评估呢？

假设文本串T和模式串P都是随即生成的，然后综合其各种组合从数学和统计等角度得出结论。

以二进制编码为例，长度为$m$的P有$2^m$ 种，长度为$m$同时在$T$中出现的P为$n-m+1<n$种。

匹配成功的概率极其低，所以并不适合作为衡量的方法。

另外一种简便策略为，随机选取文本串$T$，并从$T$中随机取出长度为$m$的子串作为模式串$P$，此为成功情况。失败情况则采用随机的模式串$P$，由此统计平均复杂度。

蛮力算法

不妨按自左向右的顺序考查各子串。在初始状态下，$T$的前$m$个字符将与$P$的$m$个字符两两对齐。接下来，自左向右检查相互对齐的这$m$对字符，若当前字符对相互匹配，则转向下一字符，反之，一旦失配，则说明在此位置文本串与模式串不可能完全匹配，于是可将$P$整体向右移动一个字符，并从其首字符开始与T中对应的新子串重新对比。

版本一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/******************************************************************************************
 * Text     :  0   1   2   .   .   .   i-j .   .   .   .   i   .   .   n-1
 *             ------------------------|-------------------|------------
 * Pattern  :                          0   .   .   .   .   j   .   .
 *                                     |-------------------|
 ******************************************************************************************/
int match ( char* P, char* T ) { //串匹配算法（Brute-force-1）
   size_t n = strlen ( T ), i = 0; //文本串长度、当前接受比对字符的位置
   size_t m = strlen ( P ), j = 0; //模式串长度、当前接受比对字符的位置
   while ( j < m && i < n ) //自左向右逐个比对字符
      if ( T[i] == P[j] ) //若匹配
         { i ++;  j ++; } //则转到下一对字符
      else //否则
         { i -= j - 1; j = 0; } //文本串回退、模式串复位
   return i - j; //如何通过返回值，判断匹配结果？
}

版本一借助整数$i$和$j$，分别指示T和P中当前接受比对的字符T[i]和P[i]。若当前字符对匹配，则i和j同时递增以指向下一对字符。一旦$j$增长到$m$则意味着发现了匹配，即可返回P相对于T的对齐位置$i-j$。一旦当前字符失配，则i回退并指向T中当前对齐位置的下一字符，同时j复位至P的首字符处，然后开始下一轮比对。

退出情况对应于整体匹配成功与否

  • 若失败，则$j<m,i=n$,$i-j$必然大于$n-m$
  • 若成功，则$j=m,i<=n$,$i-j$必然小于等于$n-m$

版本二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/******************************************************************************************
 * Text     :  0   1   2   .   .   .   i   i+1 .   .   .   i+j .   .   n-1
 *             ------------------------|-------------------|------------
 * Pattern  :                          0   1   .   .   .   j   .   .
 *                                     |-------------------|
 ******************************************************************************************/
int match ( char* P, char* T ) { //串匹配算法（Brute-force-2）
   size_t n = strlen ( T ), i = 0; //文本串长度、与模式串首字符的对齐位置
   size_t m = strlen ( P ), j; //模式串长度、当前接受比对字符的位置
   for ( i = 0; i < n - m + 1; i++ ) { //文本串从第i个字符起，与
      for ( j = 0; j < m; j++ ) //模式串中对应的字符逐个比对
         if ( T[i + j] != P[j] ) break; //若失配，模式串整体右移一个字符，再做一轮比对
      if ( j >= m ) break; //找到匹配子串
   }
   return i; //如何通过返回值，判断匹配结果？
}

版本二借助整体$i$指示$P$相对于$T$的对齐位置，并随着$i$不断递增,对齐位置逐步右移。在每一对齐位置$i$处，另一整数从$0$递增至$m-1$，依次指示当前接受比对的字符为$T[i+j]$与$P[j]$。

时间复杂度

蛮力算法在最好情况下，只需经过一轮比对，比对次数=$m=O(m)$

然而在最坏情况下，整个算法共需做$m(n-m+1)$次比对，其中$(n-m+1)(m-1)+1$次成功比对和$n-m$次失败比对。因为$m<<n$，渐进的时间复杂度为$O(nm)$。

$|\sum|$越小，最坏情况出现的概率越高，$m$越大，最坏情况的后果越严重。

实际上，在通常情况下，蛮力算法效率并不算低

任意字符比对成功的概率与失败概率分别为1/s和(s-1)/s，其中$s=|\sum|$ 为字符表的规模。每个字符各有1/s的概率出现，故任一字符串相同、不同的概率分别为1/s和(s-1)/s。

在$P$与$T$的每一对齐位置，恰好执行$k$次字符对比，当且仅当前$k-1$次成功，第$k$次失败，所以需连续执行恰好$k$次字符比对操作的概率为$(s-1)/s^k$ 。

每一次字符比对可视为一次伯努利实验，成功与失败的概率分别为$1/s$和$(s-1)/s$，而每趟的比对次数X则符合几何分布，X的期望值不超过$s/(s-1)$。在$P$和$T$的每一对齐位置，需连续比对的次数不超过$s/s-1 \leq 2=O(1)$。

直接从期望值的定义出发同样可得出相应结论，具体地，连续执行字符比对操作地次数等于所有可能的次数关于对应概率的加权平均，亦即：

$\sum_{k=1}^{m}k(s-1)/s^k=(s-1)\sum_{k=1}^{m} k/s^k=s/(s-1)$

KMP算法

蛮力算法在最坏情况下所需时间，为文本串长度与模式串长度的乘积，故无法应用于稍大的场合，很有必要改进。分析以上最坏情况，可知问题在于存在大量的局部匹配：每一轮的m次比对中，仅最后一次失配。一旦发现失配，文本串、模式串的长度都将回退，并重新开始下一轮的尝试。

实际上，这类重复的字符匹配没有必要，因为这些字符在前一轮迭代中已经接受过比对并且成功。那么，如何利用这些信息提高匹配的算法效率呢？

next表

在每轮比较进行到最后一对字符并发现失配后，蛮力算法会使两个字符指针同步后退，事实上，指针i完全不必后退。经过此前一轮的比较，已确定匹配的范围应为$P[0,j)=T[i-j,i)$

于是，若模式串经过适当右移后，可与$T$的某一子串(包含$T[i]$)完全匹配，则一项必要条件就是：

$P[0,t)=T[i-t,i)=P[j-t,j)$

亦即，在$P[0,j)$中长度为$t$的真前缀，应该与长度为$t$的真后缀完全匹配，故$t$必定来自集合:

$N(P,j)=\left{ 0\leq t<j|P[0,t)=P[j-t,j) \right}$

一般地，该集合可能包含多个这样的$t$,但是需要特别注意的是，其中具体由哪些$t$值构成仅取决于模式串P和首个比对失败的$P[j]$而与文本串无关。

若下一轮比对从$T[i]$和$P[t]$的对比开始，等效于将$P$右移$j-t$个单元。因此，为保证P和T的对齐位置，即$i$绝不倒退，同时不错过任何可能的匹配，应从集合中挑选最大的$t$。当有多个值得试探的右移方案时，应选择其中移动距离最短者。于是，若令

$next[j]=max(N(p,j))$

则一旦发现$P[j]$与$T[i]$失配，即可转而将$P[next[j]]$与$T[i]$彼此对准，并从这一位置开始继续下一轮匹配。

既然集合$N[P,j)$只取决于模式串和失配位置，而与文本串无关，作为其中的最大元素$t$必然具有这一性质。对于任一字符串，均可通过预处理将所有位置$j$所对应的$next[j]$值整理为表格以便于此后查询。

1
2
3
4
5
6
7
8
9
10
11
12
int match ( char* P, char* T ) {  //KMP算法
   int* next = buildNext ( P ); //构造next表
   int n = ( int ) strlen ( T ), i = 0; //文本串指针
   int m = ( int ) strlen ( P ), j = 0; //模式串指针
   while ( j < m  && i < n ) //自左向右逐个比对字符
      if ( 0 > j || T[i] == P[j] ) //若匹配，或P已移出最左侧（两个判断的次序不可交换）
         { i ++;  j ++; } //则转到下一字符
      else //否则
         j = next[j]; //模式串右移（注意：文本串不用回退）
   delete [] next; //释放next表
   return i - j;
}

next[0]

只要$j>0$，必有$0\in N[P,j)$，因为空串是任何非空串的子串

但若$j=0$,则有$N(P，0)= \emptyset$

不妨取$next[0]=-1$,向右移动一个字符

next[j+1]

根据已知的$next[0,j]$,如何高效地计算$next[j+1]$?

$next[j]=t$，则意味着在$P[0,j)$中，自匹配的真前缀和真后缀的最大长度为t，故必有$next[j+1] \leq next[j]+1 $,特别地，当且仅当$P[j]=P[t]$时取等号。

那么，更一般地，若$P[j]$不等于$p[t]$，又该如何得到$next[j+1]$?

由next表的功能定义，$next[j+1]$的下一候选者应该依次是

$next[next[j]]+1,next[next[next[j]]]+1,…$

因此，只需反复用$next[t]$替换$t$，即可按优先次序遍历以上候选者：一旦发现$P[j]$与$P[i]$匹配，可令$next[j+1]=next[t]+1$。既然总有$next[t]<t$,故在此过程中$t$必然严格递减，同时，即便$t$降低至$0$，亦必然会终止于通配的next[0]=-1。

next表构造算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
int* buildNext ( char* P ) { //构造模式串P的next表
   size_t m = strlen ( P ), j = 0; //“主”串指针
   int* N = new int[m]; //next表
   int t = N[0] = -1; //模式串指针
   while ( j < m - 1 )
      if ( 0 > t || P[j] == P[t] ) { //匹配
         j ++; t ++;
         N[j] = t; //此句可改进...
      } else //失配
         t = N[t];
   return N;
}

性能分析

KMP算法借助next表的确可以避免大量不必要的比对操作，但是直觉来看，在最坏情况下，共有$\Omega(n)$个对齐位置，而且在每一位置都有可能需要比对$\Omega(m)$次。实际上，在最坏情况下,KMP算法也只需运行线性时间。

考查作为字符指针的变量i和j，若令$k=2i-j$并考查k在KMP算法过程中的变化趋势，while每迭代一轮，k都会严格递增。

实际上，对应于while循环内部的if-else分支，无非两种情况：

  • 若转入if分支，则$k=2i-j$ 必将增加
  • 若转入else分支，尽管$i$不变，但在赋值$j=next[j]$之后$j$必然减小，所以$k=2i-j$必然增加

纵观算法的整个过程，启动时有$i=j=0$,即$k=0$,算法结束时$i\leq n$且$j \geq 0$，故有$k\leq 2n$。在此期间尽管$k$从0开始持续地递增，但累计增幅不过$2n$,故while循环至多执行$2n$轮。另外,while()循环体内部不含有任何循环和扽之调用，故只需$O(1)$时间。也就是说，尽管可能有$\Omega(n)$对齐位置，但就分摊意义而言，在每一对齐位置仅需$O(1)$次比对。

next表的构造算法与KMP算法并无本质区别，所以仿照上述分析可知，next表的构造算法仅需$O(m)$时间。综上可知，KMP算法的总体运行时间为$O(n+m)$。

特别适用于顺序存储介质，在单次匹配概率越大的场合，优势越明显，否则，与蛮力算法的性能相差无几。

在算法执行过程中：

  • 观察量$i$始终等于已经做过的成功比对次数(含最左端虚拟通配符的比对)次数
  • 观察量$i-j$始终不小于已经做过的失败比对次数

循环中if判断的两个分支，分别对应于成功和失败比对。其中，只有成功的比对会修改i,即i加一，当且仅当当前的比对是成功的。考虑到i初始值始终为0，始终等于成功比对的次数。

观察量i-j的初始值也是0。对于成功分支，变量i和j会同时递增一个单位，故$i-j$的数值将保持不变。而在失败分支中，观察量i不变，另一方面，必有$next[j]<j$，故在变量$j$替换为$next[j]$之后，观察量$i-j$亦必严格单调地增加。综合以上两种情况，观察量$i-j$必然可以作为失败次数的上界。

成功比对次数和失败比对次数之和即为所有比较次数。

再优化

尽管以上KMP算法可保证线性的运行时间，但在某些情况下仍然有优化的余地。

考查模式串P=”000010”

实际上，即便说$P[3]$与$T[3]$的比较还算必然，后续的这三次对比却都是不必要的，它们的失败结果早已注定。

在之前的next表中，我们利用了以往成功比对所提供的信息，将记忆力转化为预知力，但是失败比对的教训却被忽略了。

为了吸取教训，将集合$N[P,j)$的定义修改为：

$N(P,j)=\left{ 0\leq t<j|P[0,t)=P[j-t,j)\right}$ 且$P[t]!=P[j]$

除对应于自匹配长度外，$t$只有还满足当前字符对不匹配的条件方能归入集合$N[P,j)$并作为next表项的候选。

1
2
3
4
5
6
7
8
9
10
11
int* buildNext ( char* P ) { //构造模式串P的next表（改进版本）
   size_t m = strlen ( P ), j = 0; //“主”串指针
   int* N = new int[m]; //next表
   int t = N[0] = -1; //模式串指针
   while ( j < m - 1 )
      if ( 0 > t || P[j] == P[t] ) { //匹配
         N[j] = ( P[++j] != P[++t] ? t : N[t] ); //注意此句与未改进之前的区别
      } else //失配
         t = N[t];
   return N;
}

BM算法

KMP算法的思路可概括为：当前比对一旦失配。即利用此前的比对(无论成功或失败)所提供的信息，尽可能长距离地移动模式串。无需显式地反复保存或更新比对的历史，而是独立于具体的文本串，事先根据模式串预测出所有可能出现的失配情况。

串匹配过程为多次失败的对齐和0/1次成功的对齐。就单个对齐位置的排除而言，平均只需常数次比对，且具体的比对位置和次序无所谓。然而就排除更多后续位置而言，不同的对比位置及次序，作用差异极大。其中，越是靠前/后的位置，作用越小/大。

BM算法中，模式串P与文本串T的对准位置依然自左向右推移，而在每一对准位置却是自右向左地逐一比对各个字符。在每一轮自右向左的比对过程中，一旦发现失配，则将P右移一定距离并再次与T对准，然后重新一轮自右向左的扫描比对。

BM算法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int match ( char* P, char* T ) { //Boyer-Morre算法（完全版，兼顾Bad Character与Good Suffix）
   int* bc = buildBC ( P ); int* gs = buildGS ( P ); //构造BC表和GS表
   size_t i = 0; //模式串相对于文本串的起始位置（初始时与文本串左对齐）
   while ( strlen ( T ) >= i + strlen ( P ) ) { //不断右移（距离可能不止一个字符）模式串
      int j = strlen ( P ) - 1; //从模式串最末尾的字符开始
      while ( P[j] == T[i + j] ) //自右向左比对
         if ( 0 > --j ) break; /*DSA*/showProgress ( T, P, i, j ); printf ( "\n" ); getchar();
      if ( 0 > j ) //若极大匹配后缀 == 整个模式串（说明已经完全匹配）
         break; //返回匹配位置
      else //否则，适当地移动模式串
         i += __max ( gs[j], j - bc[ T[i + j] ] ); //位移量根据BC表和GS表选择大者
   }
   delete [] gs; delete [] bc; //销毁GS表和BC表
   return i;
}

其中借助了整数i和j指示文本串中当前对齐位置T[i]和模式串中接受比对的字符P[j]。不过，一旦局部失配，根据bc表和gs表确定最大的安全移动距离。为此，需要通过预处理，根据模式串P整理出坏字符和好后缀两类信息。

坏字符

若当前模式串P当前在文本串中的对齐位置为i，且在这一轮自右向左将P和substr(T,i,m)的比对过程中，在P[j]处首次发现失配：$T[i+j] =X \neq Y=P[j]$，则将$X$称为坏字符。

若P与T的某一子串(包括$T[i+j]$在内)匹配，则必然在$T[i+j]=X$中匹配，反之，若与$T[i+j]$对准的字符不是X,则必然失配。只需找出P中的每一字符X，分别与$T[i+j]=X$对准，并执行一轮从右向左的扫描比对。对应每个这样的字符，P的位移量仅取决于原来失配位置$j$，以及$X$在P中的秩，而与$T$和$i$​无关。

bc表

若P中含有多个X,仅尝试p中最靠右的字符X(若存在)。如此可在确保不致遗漏匹配的前提下，始终单向地滑动模式串。若P中最靠右的字符X为$P[k]=X$,则P的右移量为$j-k$。

对于任一给定的模式串P，$k$值只取决于字符$T[i+j]=X$,因此可视为从字符表到整数(P中字符的秩)的一个函数

$bc(x)=$

  • $k$，若$P[k]=x$,且对所有的$i>k$都有$p[i]!=c$
  • $-1$,若P中不含字符$c$

若当前对齐位置为$i$，则一旦出现坏字符$P[j]=Y$,则重新对齐于$i+=j-bc[T[i+j]]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//*****************************************************************************************
//    0                       bc['X']                                m-1
//    |                       |                                      |
//    ........................X***************************************
//                            .|<------------- 'X' free ------------>|
//*****************************************************************************************
int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256)
   int* bc = new int[256]; //BC表，与字符表等长
   for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现
   for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P
      bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法
   /*DSA*/printBC ( bc );
   return bc;
}

该算法在对BC表初始化后，对模式串做一遍线性扫描，并不断用当前字符的秩更新BC表中的对应项。因为是按照秩递增的顺序从左到右扫描，所以只要c在P中出现过，则最终的BC表将记录下其中最靠右的秩。

运行时间可划分为两个部分，分别消耗于其中的两个循环，前者是对字符表中每个字符进行初始化，时间不超过$O(|\sum|)$ 。后一循环对模式串P做一轮扫描，其中每个字符消耗$O(1)$时间，故共需$O(m)$时间。由此可知，BC表可在$O(|\sum|+m)$时间内构造出来，其中$|\sum|$为字符表的规模，m为模式串的长度。

暂且不计构造BC表的过程，BM算法本身进行串模式匹配所需时间与具体的输入十分相关。若将文本串和模式串的长度分别记作n和m，则在通常情况下实际运行时间往往低于$O(n)$。在最好情况下，每经过常数次比对就可以将模式串整体向右移动m个字符，此类情况下只需$O(n/m)$次比对算法即可终止，故运行时间不过$ O(n/m)$。

在最坏情况下，每轮迭代都需要在扫过整个P之后，方能确定右移一个字符，须经过m次比较，方能排除单个对齐位置，时间复杂度为$ O(nm) $。

单次匹配概率越大的场合，性能越接近蛮力算法。

针对坏字符在模式串中的位置太过于靠右，以至位移量为负的情况，建议将P右移一个字符，此后并不能保证坏字符出恢复匹配，可在P[j]的左侧找到最靠右的字符并将其与原坏字符对齐。

以上思路的实现方式等效于将原来一维的bc表，替换为二维的bc表，具体地，这是一张m*$|\sum|$ 的表格。尽管预处理时间和所需空间增长量并不大，但是匹配算法的控制流程却进一步复杂化。最重要的是，此类二维bc表若能发挥作用，则当时的好后缀必然很长，此类情况同时使用的gs表必然可以代替bc表。

好后缀

参照KMP算法的思路，坏字符策略仅仅利用了此前失败比对所提供的教训而忽视了成功的比对。类似于KMP算法，只不过前后颠倒而已。

每轮比对中的若干次成功匹配，都对应于模式串P的一个后缀，称为好后缀(good suffix)。

一般地，设本轮自右向左的扫描匹配终止于失配位置：

$T[i+j]=X \neq Y=P[j]$

若分别记

$W=substr(T,i+j+1,m-j-1)=T[i+j+1,m+i)$

$U=suffix(P,m-j-1)=P[j+1,m)$

则$U$为当前的好后缀，$W$为$T$中与之匹配的子串。好后缀的长度为m-j-1,故只要$j\leq m-2$,则$U$必然非空，$U=W$。

此时若存在某一整数，使得在将P整体右移j-k个单元，并使$P[k]$与$T[i+j]$相互对齐之后，$P$可以与文本串的某一子串(包括$T[m+j-1]$在内)匹配，亦即

$P=substr(T,i+j-k,m)=T[i+j-k,m+i+j-k)$

于是，若记：

$V(k)=substr(P,k+1,m-j-1)=P[k+1,m-j+k)$

必然有$V(k)=W=U$

也就是说，若值得将$P[k]$与$T[i+j]$对齐并做新的一轮比对，则P的子串首先必须和P自己的后缀U相匹配。

另外，还有一必要条件，P中这两个匹配的子串的前驱字符不得相等，即P[k]$\neq$ P[j],与之前类似，在此处必将再次失败。

若模式串存在多个满足上述必要条件的子串V(k),不妨选取其中最靠右者(对应最大的$k$,最小的右移距离$j-k$)。

若P中不存在任何子串与U完全匹配，则从P的所有前缀中，找出可与U的某一真后缀相匹配的最长者作为V(k)，并取$gs[j]=m-|V(k)|$。

与之前类似，位移量只取决于$j$和$P$本身，亦可预先计算并制表待查。

gs表

蛮力算法

根据以上定义，可导出gs表构造算法如下：

对于每个好后缀$P(j,m)$，按照从后向前($k$从$j-1$递减至0)的次序，将其与P的每个子串$P(k,m+k-j)$一一对齐，并核对是否出现匹配，一旦出现，对应的位移量即为$gs[j]$的取值。

这里共有$O(m)$个好后缀，可与$O(m)$个子串相互对齐，每次对齐后在最坏情况下需要比对$O(m)$次，因此该算法可能需要$O(m^3)$次。

实际上，仅需线性时间即可构造出gs表。

ss表

对于任一整数$j\in[0,m)$,在$P[0,j]$的所有后缀中，考查那些与P的某一后缀匹配者。若将其中最长者记作MS[j]，则$ss[j]$就是该串的长度$|MS[j]|$.特别地，在$MS[j]$不存在时，取$ss[j]=0$。

综上所述，可定义$ss[j]$如下：

$ss[j]=max{ 0\leq s\leq j+1|P(j-s,j]=P[m-s,m)}$

特别地，当$j=m-1$时，必有$s=m$，此时，有$P(-1,m-1]=P[0,m)$

任一字符$P[j]$对应的$ss[j]$值，可分两种情况提供有效的信息：

  • $ss[j]=j+1$ 也就是说MS[j]就是整个前缀，后缀长度应该大于$j+1$，所以此时对应于$P[m-j-1]$左侧的每个字符$P[i]$而言，$P[m-1]$下一步可与$P[j]$对齐，所以$m-j-1$都应是$gs[i]$取值的一个候选。
  • $ss[j] \leq j MS[j]$只是$P[0,j]$的一个真后缀。同时，既然$MS[j]$是极长的，故必有：$P[m-ss[j]-1]\neq P[j-ss[j]]$ ,此时的字符$m-j-1$也应是$gs[m-ss[j]-1]$取值的一个候选

根据此前定义，每一位置i所对应的gs[i]值只可能来自于以上候选。

ss表的构造

由上可见，ss表的确是构造gs表的基础和关键，同样，若采用蛮力策略，则对每个字符$P[j]$都需要做一趟扫描对比，直到出现失配。如此，累计需要$O(m)$时间。

为了提高效率，不妨从后至前逆向扫描，并逐一地计算出各字符$P[j]$对应的$ss[j]$的值。

通过$lo,hi$来动态记录当前的极长匹配后缀：$P(lo,hi]=P[m-hi+lo,m)$

此时必有$P[j]=P[m-hi+j-1]$,故可利用此前已经计算的$ss[m-hi+j-1]$，分两种情况快速得导出$ss[j]$

  • 如图(a)所示，$ss[m-hi+j-1]\leq j-lo$,此时，$ss[m-hi+j-1]$也是$ss[j]$可能的最大取值，可直接得到$ss[j]=ss[m-hi+j-1]$。
  • 如图(b)所示，$j-lo<ss[m-hi+j-1]$，此时，至少仍有$P(lo,j]=P[m-hi+lo,m-hi+j)$,故只需将$p[j-ss[m-hi+j-1],lo]$与$P[m-hi+j-ss[m-hi+j-1],m-hi+lo]$做一比对，也可确定$ss[j]$。

由以上构思，可在$O(m)$时间内构造出ss表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m)
   int m = strlen ( P ); int* ss = new int[m]; //Suffix Size表
   ss[m - 1]  =  m; //对最后一个字符而言，与之匹配的最长后缀就是整个P串
// 以下，从倒数第二个字符起自右向左扫描P，依次计算出ss[]其余各项
   for ( int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j -- )
      if ( ( lo < j ) && ( ss[m - hi + j - 1] <= j - lo ) ) //情况一
         ss[j] =  ss[m - hi + j - 1]; //直接利用此前已计算出的ss[]
      else { //情况二
         hi = j; lo = __min ( lo, hi );
         while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？
            lo--; //逐个对比处于(lo, hi]前端的字符
         ss[j] = hi - lo;
      }
   return ss;
}

暂且忽略内循环，首先考查外循环，若将j作为其控制变量，则不难验证

  1. $j$的初始值为$m-2$
  2. 每经过一步迭代，$j$都会递减一个单位
  3. 在其他任何语句中，$j$都没有作为左值被修改
  4. 一旦$j$减至负数，外循环随即终止

由此可知，外循环至多迭代$O(m)$步，累计耗时$O(m)$。

尽管从表面的形式来看，外循环的每一步都有可能执行一趟内循环，但实际上所有的内循环累计运行时间也不超过$O(m)$。为此，只需将lo视为其控制变量，则不难验证：

  1. $lo$的初始值为$m-1$
  2. 每经过一步内循环的迭代，$lo$值都会递减一个单位
  3. 在其他部分，$lo$只能在lo=__min ( lo, hi ) 一句中作为左值被修改，但仍是非增
  4. 一旦$lo$减至负数，内循环就不再启动

由此可知，内循环至多迭代$O(m)$步，相应地，累计耗时不过$O(m)$。

1
2
3
4
5
6
7
8
9
10
11
12
int* buildGS ( char* P ) { //构造好后缀位移量表：O(m)
   int* ss = buildSS ( P ); //Suffix Size table
   size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table
   for ( size_t j = 0; j < m; j ++ ) gs[j] = m; //初始化
   for ( size_t i = 0, j = m - 1; j < UINT_MAX; j -- ) //逆向逐一扫描各字符P[j]
      if ( j + 1 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则
         while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]而言（二重循环？）
            gs[i++] = m - j - 1; //m - j - 1都是gs[i]的一种选择
   for ( size_t j = 0; j < m - 1; j ++ ) //画家算法：正向扫描P[]各字符，gs[j]不断递减，直至最小
      gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的一种选择
   delete [] ss; return gs;
}

以j为外循环的控制变量，则可知外循环至多迭代$O(m)$步，以i作为内循环的控制变量，可知内循环累计至多迭代$O(m)$步，累计耗时$O(m)$。

在模式枚举类应用中，需要从文本串T中找出所有的模式串P，有时允许两次出现的位置不超过m个字符。比如在000000中查找000，若限制多次出现的模式串之间至少相距3个字符，则应找到2处匹配，若不加以限制，则应找到4处匹配。在这种情况下，最坏情况下复杂度可能达到$O(nm)$。

可通过Galil规则对上述情况改进，总体耗时不致于超过线性的规模。

性能分析

空间复杂度为$|bc[]|+|gs[]|=O(|\sum|+m)$

预处理的时间为$O(|\sum|+m)$

查找在最好情况下为$O(n/m)$，最差情况下为$O(n+m)$

在通常情况下，单次比对的成功概率直接取决于字符集的规模。当字符集规模较小时，单次比对的成功概率较高，蛮力算法的效率低。此时，KMP算法稳定的线性复杂度更能体现出优势，而采用BC表的BM算法并不能大跨度地向前移动。

反之，若字符串的规模较大，则单词比对的成功概率较小，蛮力算法也可接近线性复杂l度，此时，尽管KMP算法仍然保持线性复杂度，但相对而言的优势并不明显，而采用BC表的BM算法则会因为比对失败概率的增加，从而大跨度地向前移动。

最好情况 最坏情况 特点l
蛮力算法 $ O(n)$ $ O( nm )$ 适用于规模较大的字符集，通常情况下实际运行效率不低
KMP算法 $ O(n+m)$ $O(n+m)$ 适用于规模较小的字符集，字符集规模较大时与蛮力算法不相上下
BM算法(bc) $O(n/m )$ $O( nm)$ 适用于规模较大的字符集，性能浮动范围大
BM算法(bc+gs) $O(n/m)$ $ O(n+m)$ 四种算法中最优

Karp-rabin算法

将任一有限字符串视作自然数，进而在字符串和自然数之间建立联系。若字符串规模$|\sum|$ 对应于一个$d+1$进制的整数。

以由大写英文字母组成的字母表为例，若将这些字符表依次映射为[1,26]内的自然数，则每个这样的字符串都将对应于一个26+1=27进制的整数，比如：

$CANTOR \leq 3,1,14,20,15,18\geq43,868,727(10)$

以上散列并非满射，但是不含’0’的任一$d+1$进制值自然数，唯一地对应于某个字符串。字符串经如此转换得到的散列码，称为其指纹。之所以取$d+1$而不是$d$，是为了回避’0’字符以保证这一映射为单射，否则若字符串中存在由’0’字符组成的前缀，则无论该前缀长度如何，都不会影响对应的整数取值。

由此可将判断模式串是否与文本匹配的问题转换为判断T中是否由某个子串相同的指纹的问题，具体地，只要逐一取出T中长度为m的子串，并将其对应的指纹与P所对应的指纹一一比对即可确定是否存在匹配位置，称为karp-robin算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int match ( char* P, char* T ) { //串匹配算法（Karp-Rabin）
   size_t m = strlen ( P ), n = strlen ( T ); //assert: m <= n
   HashCode Dm = prepareDm ( m ), hashP = 0, hashT = 0;
   for ( size_t i = 0; i < m; i++ ) { //初始化
      hashP = ( hashP * R + DIGIT ( P, i ) ) % M; //计算模式串对应的散列值
      hashT = ( hashT * R + DIGIT ( T, i ) ) % M; //计算文本串（前m位）的初始散列值
   }
   for ( size_t k = 0; ; ) { //查找
      if ( hashT == hashP ) 
         if ( check1by1 ( P, T, k ) ) return k;
      if ( ++k > n - m ) return k; //assert: k > n - m，表示无匹配
      else updateHash ( hashT, T, m, k, Dm ); //否则，更新子串散列码，继续查找
   }
}

算法除了预先计算模式串指纹hash(P)等预处理，至多包含$|T|-|P|=n-m$次迭代，每轮都需计算当前子串的指纹。

然而，若字符集规模较大，模式串P较长，其对应的指纹将很大。若指纹的长度无法在常数时间内完成，总体需要$O(nm)$时间。

散列压缩

通过对比压缩后的指纹，确定匹配位置，借助散列将指纹压缩至存储器支持的范围。比如，采用模余函数：$hash(key)=key % M$

经过散列压缩后指纹比对的时间将仅取决于散列表长，而与模式串长m无关。

散列冲突

hash()值相等，并非匹配的充分条件，压缩散列空间的时候必然引起冲突。文本串中不同子串的指纹可能相同，甚至都恰好与模式串相同。因此，通过hash()筛选之后，还须经过严格比对，方可确定是否匹配。

1
2
3
4
5
bool check1by1 ( char* P, char* T, size_t i ) { //指纹相同时，逐位比对以确认是否真正匹配
   for ( size_t m = strlen ( P ), j = 0; j < m; j++, i++ ) //尽管需要O(m)时间
      if ( P[j] != T[i] ) return false; //但只要散列得当，调用本例程并返回false的概率将极低
   return true;
}

适当选取散列函数可大大降低冲突的可能。

指纹更新

可根据前一子串和后一子串的指纹，在常数时间内得到后一子串的指纹。整个算法过程中，消耗与子串计算的时间，平均每次仅为常数时间。

1
2
3
4
5
6
7
8
9
10
11
// 子串指纹快速更新算法
void updateHash ( HashCode& hashT, char* T, size_t m, size_t k, HashCode Dm ) {
   hashT = ( hashT - DIGIT ( T, k - 1 ) * Dm ) % M; //在前一指纹基础上，去除首位T[k - 1]
   hashT = ( hashT * R + DIGIT ( T, k + m - 1 ) ) % M; //添加末位T[k + m - 1]
   if ( 0 > hashT ) hashT += M; //确保散列码落在合法区间
}
HashCode prepareDm ( size_t m ) { //预处理：计算R^(m - 1) % M （仅需调用一次，不必优化）
   HashCode  Dm = 1;
   for ( size_t i = 1; i < m; i++ ) Dm = ( R * Dm ) % M; //直接累乘m - 1次，并取模
   return Dm;
}