数据结构学习笔记(九)串及模式匹配算法

字符串在实际中有极为广泛的应用，在文字编辑、信息检索、语言编译等软件系统中，字符串均是重要的操作对象；在网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配，也称模式匹配。

研究者已收集了大量的病毒DNA和人的DNA数据，想快速检测出这些人是否感染了相应的病毒。为了方便研究，研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。（注意，人的DNA序列是线性的，而病毒的DNA序列是环状的）

一、 串的类型定义

串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为：

s=“ … ”(n≥0)

其中，s是串的名，用双引号括起来的字符序列是串的值；ai(1≤i≤n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串（null string），其长度为零。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，例如，在线性表中查找某个元素，求取某个元素，在某个位置上插入一个元素或删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，例如，在串中查找某个子串，求取一个子串，在串的某个位置上插入一个子串，以及删除一个子串等。

二、串的存储结构

与线性表类似，串也有两种基本存储结构：顺序存储和链式存储。但考虑到存储效率和算法的方便性，串多采用顺序存储结构。

1、串的顺序存储类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述：

//串的定长顺序存储结构
#define MAXLEN 255     //串的最大长度
Typedef struct{
 Char ch[MAXLEN+1];     //串的长度
 Int length;
}

其中，MAXLEN表示串的最大长度，ch是存储字符串的一维数组，每个分量存储一个字符，length表示字符串的当前长度。

为了便于说明，本内容算法描述当中所用到的顺序存储的字符串都是从下标为1的数组分量开始存储。

以上定义方式是静态的，在编译时就确定了串空间的大小。而多数情况下，串的操作是以串的整体形式参与的，串变量之间的长度相差较大，在操作中串值长度的变化也较大，这样为串变量设定固定大小的空间不尽合理。因此最好是根据实际需要，在程序执行过程中动态地分配和释放字符数组空间。

在C语言中，存在一个称之为“堆”（Heap）的自由存储区，可以为每个新产生的串动态分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时为了以后处理方便，约定串长也作为存储结构的一部分。这种字符串的存储方式也称为串的堆式顺序存储结构，定义如下：

//串的堆式顺序存储结构
Typedef struct{
 Char *ch;     // 若是非空串，则按串长分配存储区，否则ch为NULL
 Int  length;
}HString;

2、串的链式存储顺序串的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表方式存储串。由于串结构的特殊性——结构中的每个数据元素是一个字符，则在用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

例如，图（a）所示为结点大小为4（即每个结点存放4个字符）的链表：

图（b）所示为结点大小为1的链表。

当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符（通常“#”不属于串的字符集，是一个特殊的符号）。

为了便于进行串的操作，当以链表存储串值时，除头指针外，还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构，说明如下：

/* 串的块链存储结构 */
#define CHUNKSIZE 80
typedef struct Chunk {
    char ch[CHUNKSIZE];  // 当前块中的内容
    struct Chunk* next;  // 指向下一个块
} Chunk;

/* 串的块链存储类型定义 */
typedef struct {
    Chunk* head;    //串的头指针
    Chunk* tail;    //串的尾指针
    int length;     //串的当前长度
} LString;

在链式存储方式中，结点大小的选择直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或很多，如一本书的几百万个字符，图书馆的成千上万条目录，这就要求考虑串值的存储密度。

显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。如果在串处理过程中需进行内、外存交换的话，则会因为内、外存交换操作过多而影响处理的总效率。应该看到，串的字符集的大小也是一个重要因素。一般来说，字符集小，则字符的机内编码就短，这也影响串值存储方式的选取。

串值的链式存储结构对某些串操作，如联接操作等，有一定方便之处，但总地说来，不如顺序存储结构灵活，它占用存储量大且操作复杂。此外，串值在链式存储结构时，串操作的实现和线性表在链表存储结构中的操作类似，本文不作详细讨论。

三、串的模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。此运算的应用非常广泛，比如在搜索引擎、拼写检查、语言翻译、数据压缩等应用中，都需要进行串匹配。一般采用串的定长顺序存储结构实现的。

串的模式匹配设有两个字符串S和T，设S为主串，也称正文串；设T为子串，也称为模式。在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在主串S中出现的位置。

著名的模式匹配算法有BF算法和KMP算法，下面详细介绍这两种算法。

1、BF算法

最简单直观的模式匹配算法是BF（Brute-Force）算法。模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置pos。如果采用字符串顺序存储结构，可以写出不依赖于其他串操作的匹配算法。

【算法步骤】

① 分别利用计数指针i和j指示主串S和子串T中当前正待比较的字符位置，i初值为pos，j初值为1。

② 如果两个串均未比较到串尾，即i和j均分别小于等于S和T的长度时，则循环执行以下操作：

S.ch[i]和T.ch[j]比较，若相等，则i和j分别指示串中下个位置，继续比较后续字符；

若不等，指针后退重新开始匹配，从主串的下一个字符（i=i-j+2）起再重新和子串的第一个字符（j=1）比较。

如果j>T.length，说明子串T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和子串T中第一个字符相等的字符在主串S中的序号（i-T.length）；否则称匹配不成功，返回0。

【算法描述】

//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0  
//其中，T非空，
int Index_BF(SString S,SString T,int pos){
1≤pos≤S.length    
i=pos; j=1;                         //初始化    
while(i<=S.length && j<=T.length)  //两个串均未比较到串尾    
{        
if(S[i].ch==T[j].ch)
{
++i;
++j;
}                           //继续比较后继字符        
Else{i=i-j+2;j=1;}          //指针后退重新开始匹配    
}       
if(j>T.length) 
return i-T.length;  //匹配成功    
else 
return 0;               //匹配失败
}

下图展示了子串T=“abcac”和主串S的匹配过程（pos=1）。

【算法分析】

BF算法的匹配过程容易理解，且在某些应用场合效率也较高。在匹配成功的情况下，考虑以下两种极端情况。

（1）最好情况下，每趟不成功的匹配都发生在子串的第一个字符与主串中相应字符的比较。例如：

S=“aaaaaba”

T=“ba”

设主串的长度为n，子串的长度为m，假设从主串的第i个位置开始与子串匹配成功，则在前i?1趟匹配中字符总共比较了i?1次；若第i趟成功的字符比较次数为m，则总比较次数为i?1+m。对于成功匹配的主串，其起始位置由1到n?m+1，假定这n?m+1个起始位置上的匹配成功概率相等，则最好的情况下匹配成功的平均比较次数为

（2）最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符与主串中相应字符的比较。

例如：S=“aaaaaab”

T=“aab”

假设从主串的第i个位置开始与模式串匹配成功，则在前i?1趟匹配中字符总共比较了(i?1) ×m次；若第i趟成功的字符比较次数为m，则总比较次数i ×m。因此最坏情况下匹配成功的平均比较次数为

即最坏情况下的平均时间复杂度是O(n ×m)。BF算法思路直观简明。但当匹配失败时，主串的指针i总是回溯到i?j+2位置，模式串的指针总是恢复到首字符位置j=1，因此，算法时间复杂度高。下面将介绍另一种改进的模式匹配算法。

2、KMP算法

KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者。

KMP算法要解决的问题就是在字符串（也叫主串S）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串(子串）就是关键字（接下来称它为T），如果它在一个主串（接下来称为S）中出现，就返回它的具体位置，否则返回0（常用手段）。

上面用BF算法是没有问题的，但不够好！如上面的匹配，A和E不相等，那就把i指针移回第2位（假设下标从1开始），j移动到模式串的第1位，然后又重新开始这个步骤：

如果是人的思维来匹配的话，肯定不会再把i移动回第1位，因为主串匹配失败的位置前面除了第一个A之外再也没有A了，我们为什么能知道主串前面只有一个A？因为我们已经知道前面三个字符都是匹配的！，而且这4个字符都不相同（这很重要）。移动过去肯定也是不匹配的！有一个想法，i可以不动，我们只需要移动j即可，如下图：

上面的这种情况还是比较理想的情况，我们最多也就多比较了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”，比较到最后一个才知道不匹配，然后i回溯，这个的效率是显然是最低的。

于是三个大牛研究出了KMP算法。其思想就如同我们上边所看到的一样：“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”

所以，假设主串为“s1s2…sn”，子串为“t1t2…tm”，整个KMP的重点就在于当某一个子串字符与主串不匹配时，我们应该知道j指针要移动到哪？

接下来我们自己来发现j的移动规律：

如图：C和D不匹配了，保持i指针不动，我们要把j移动到哪？显然是第2位。为什么？因为前面有一个A与主串中第3个A相同：

如下图也是一样的情况：

可以把j指针移动到第3位，因为前面有两个字母是一样的：

至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。

如果用数学公式来表示是这样的：

P[0 ~ k-1] == P[j-k ~ j-1]

这个相当重要，如果觉得不好记的话，可以通过下图来理解：

这个很重要，我是花了好多时间，才明白为什么可以直接将j移动到k位置了。这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。

好，接下来就是重点了，怎么求这些k呢？因为在子串T的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当S[i] != T[j]时，j指针的下一个位置。

若令next[j]=k，则next[j]表明当子串中第j个字符与主串中相应字符“失配”时，在子串中需重新和主串中该字符进行比较的字符的位置。由此可引出子串的next函数的定义：

看了很多书，在这个地方都是讲得比较含糊或是根本就一笔带过，甚至就是贴一段代码上来，为什么这段代码是这样？怎么确认j指针的下一个位置，根本就没有说清楚。而这里恰恰是KMP算法最关键的地方。

我们自己来推导思路，现在要始终记住一点，next[j]的值（也就是k）表示，当S[i] != T[j]时，j指针的下一步移动位置。

如何具体推导出一个子串（模式串）的next数组的值？假如：子串：T=”abcac”

分析如下：

（1）当j=1,next[1] = 0;

（2）当j=2，j由1到是j-1就只有字符“a”，属于其他情况next[2]=1;

（3）当j=3，j由1到是j-1就只有字符“ab”，显然”a”与”b ”不相等，属于其他情况next[3]=1;

（4）当j=4，j由1到是j-1就只有字符“aba”，显然前缀字符”a”，与后缀字符”a”相等，next[4]=2;

（5）当j=5，j由1到是j-1就只有字符“abaa”，显然前缀字符”a”，与后缀字符”a”相等，属于其他情况next[5]=2;

（6）当j=6，j由1到是j-1就只有字符“abaab”，显然前缀字符”ab”，与后缀字符”ab”相等，next[6]=3;

（7）当j=7，j由1到是j-1就只有字符“abaabc”，显然前缀字符”a”，与后缀字符”c”不相等，属于其他情况next[7]=1;

（8）当j=5，j由1到是j-1就只有字符“abaabca”，显然前缀字符”a”，与后缀字符”a”相等，属于其他情况next[8]=2;

由此我们可以根据公式得到，如果前后缀一个字符相等，k=next[j]的值就是2，如果两个字符相等，k=next[j]就是3，后面以些类推。

计算next函数值，算法描述如下：

void get_next(String T,int next[])
{//求子串T的next函数值并存入数组next   
i=1;
j=0；  
next[1]=0; 
while(i<T.length)   
{     
if(j==0‖T.ch[i]==T.ch[j]){++i;++j;next[i]=j;
}     
else j=next[j];    
}
}

以上面BF算法的匹配过程，我们用KMP算法来推导，next[j]函数值如下：

第一趟，当i=3,j=3时，字符”a”与”c”不相等，

根据上面算法：j= next[j]；得出j = next[3]=1,则next指针下一个值从j=1开始：

i指针继续右移，j指针也从1开始，当i=7,j=5时，字符”b”与”c”不相等，则j=next[5]=2,则next指针下一个值从j=2开始：

第三趟匹配成功，程序结束，返回匹配位置。

在求得子串的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和子串中正待比较的字符，令i的初值为pos，j的初值为1。若在匹配过程中si=tj，则i和j分别增1，否则，i不变，而j退到next［j］的位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依次类推，直至下列两种可能：

（1）一种是j退到某个next值时字符比较相等，则指针各自增1，继续进行匹配；

（2）另一种是j退到值为零（即子串的第一个字符“失配”），则此时需将子串继续向右滑动一个位置，即从主串的下一个字符i+1起和模式重新开始匹配。

KMP算法描述如下：

int Index_KMP(SString S,SString T,int pos)
{//利用模式串T的next函数求T在主串S中第pos个字符之后的位置     
//其中，T非空，1≤pos≤S.length    
i=pos;j=1;       
while(i<=S.length && j<=S.length)   //两个串均未比较到串尾    
{          
if(j==0‖S[i]==T[j]){++i;++j;}     //继续比较后继字符          
else j=next[j];                   //模式串向右移动       
}       
if(j>T[0]) return i-T[0];           //匹配成功       
else return 0;                      //匹配失败
} 	

KMP 匹配算法时间复杂度为O(m)。通常，模式串的长度m比主串的长度n要小得多，因此，对整个匹配算法来说，所增加的这点时间是值得的。

但是，前面定义的next函数在某些情况下尚有缺陷。例如模式“aaaab”在和主串“aaabaaaab”匹配时，当i=4、j=4时s.ch[4]≠t.ch[4]，由next[j]的指示还需进行i=4、j=3，i=4、j=2，i=4、j=1这3次比较。实际上，因为模式中第1～3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式连续向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。

next函数修正值如下：

void get_nextval(String T，int nextval[])
{//求模式串T的next函数修正值并存入数组nextval   
i=1;nextval［1］=0;j=0;   
while(i<T.length)   
{     
if(j==0‖T.ch[i]==T.ch[j])     
{        
  ++i;
  ++j;                 
if(T.ch[i]!=T.ch[j]) 
nextval[i]=j;        
else  nextval[i]=nextval[j];     
}         
else j=nextval[j];   
}
}