数据结构（六）串

串（String）是由零个或多个字符串组成的有限序列，一般记为 s = ‘a1a2…an’ (n ≥ 0) 其中，s是串名，单引号括起来的字符序列是串的值，ai(1 ≤ i ≤ n)可以是字母，数字或者其他字符，n为串的长度。

几个概念

• 空串（null string） ：零个字符的串
• 子串 ：串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串
• 位置：字符在序列中的序号被称为该字符在串中的位置；子串在主串中的位置则以子串的第一个字符在主串中的位置来表示
• 若两个串长度相等且每个对应位置的字符都相等时，称这两个串是相等的
• 空格串（blank string）：由一个或多个空格组成的串（注：不是空串）

这里的串指的是一种逻辑结构，注意与C语言中的字符串区别。

串的表示

1.定长顺序存储表示

#define MAXSIZE 255
typedef struct

{
    char ch[MAXSIZE];
    int  length;
}SString;

这种存储方式类似于线性表的顺序存储，用地址连续的存储单元存储字符序列。串的长度可以在预定长度范围内随意取，超过预定长度的值被舍去。

2.堆分配存储表示

typedef struct
{
    char *ch;
    int  length;
}HString;

这种存储方式以一组地址连续的存储单元存放串值，但存储空间的分配是动态进行的。例如在C语言中用malloc()和free()来动态管理存储空间。

3.块链存储表示

#define CHUNKSIZE 80
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct
{
    Chunk *head,*tail; /* 串的头和尾指针 */
    int  curlen;       /* 串的当前长度 */
}LString;

和线性表的链式存储结构类似，串值也可以用链表存储。在这里要注意的是定义的结点可存放字符的长度可不同。

串的常见基本操作

（1）串的赋值 （2）两组串的比较 （3）求串长 （4）联接串 （5）求子串

这里只是例举了串比较常见的操作，还有其他操作读者感兴趣可以自行查询资料。

串的模式匹配算法

（1）求子串位置的定位函数Index(S,T,pos)

子串的定位操作通常被称作为串的模式匹配（其中S称为主串，T称为模式串），是各种串处理系统中最重要的操作之一。

具体操作如下图所示：

图1 串模式匹配示意

算法思想：

从主串S的pos位置开始的字符与模式串的第一个字符开始比较，若相等则继续对比后面的字符，若不相等则从主串下一个字符开始与模式串第一个字符重新开始比较，直至找到相等的字符序列，则匹配成功，返回第一个字符所在位置，否则返回-1。

（注：位置标号从1开始）

int Index(SString S,SString T,int pos)
{
    int i,j;
    i = pos;    /* 主串开始比对位置 */
    j = 1;

    while((i <= S.length) && (j <= T.length))
    {
        if(S.ch[i - 1] == T.ch[j - 1])
        {
            /* 继续比较后续字符 */
            i ++;
            j ++;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    
    if(j > T.length)
    {
        return (i - T.length);
    }
    else
    {
        return (-1);
    }
}

这种匹配过程易于理解，在文本编辑等应用场合效率也比较高。但是在有些情况下，该算法效率就很低。例如，假设模式串为'00000001'，主串为'0000...000001'（主串前面有52个0），在每次对比的过程中都是对比到模式串的最后一个字符才能发现不一致，接着再从主串下一个字符开始重新比较，这样while循环次数为46次，每一次while循环中又对比了8次，时间复杂度为O(46 * 8)，显然效率是不高的。

（2）KMP算法（改进的字符串匹配算法）

此算法可以在时间复杂度为O(n+m)（n为主串长度，m为模式串长度）的时间数量级上完成串的模式匹配。其内涵主要在于当匹配过程中出现不相等的字符，也可以根据已经匹配过的部分尽可能快的定位到模式串中下一次开始匹配的位置，其中i没有进行回溯。

首先先要介绍两个概念：

前缀：指一个串中，除最后一个字符外，包含的所有子串的集合

后缀：指一个串中，除第一个字符外，包含的所有子串的集合

部分匹配值：字符串前缀和后缀相等的部分的最长的长度值

下面来看一个例子：

图2 前后缀示意图

图2中，前缀和后缀集合中没有相等的部分，所以部分匹配值为0。

那么前缀和后缀这个概念的引入有什么用，我们先来想一下，如果这两个字符串让我们自己去比较找出匹配字符段，我们会怎么做（先不要用程序思维去思考），我觉得我们会按照下图这样去做：

图3 主串、模式串匹配示意

假设这两个字符串我们分别写在两张小纸条上，对比的时候我们会主串向左拉，模式串向右拉，一个一个比较，如果嫌慢的话，在第一次比较到i=3的位置，我们会一眼看到模式串的开头画红圈的a和主串画红圈的a一样，所以我们会直接把模式串的第一个字母a拉到主串第3个字母，可以从上图看出，在匹配的时候，模式串我们是从前端开始对比，而和模式串进行对比的主串我们总是从后端开始对比，因为之前对比过的部分，在“失配”之前主串和模式串上的字符是一样的，我们就可以只将模式串拿出来对比前、后缀即可。这大概可能就是引入前缀后缀的意义。（此部分纯属笔者脑补，如有错误概不负责~）

有了上面的预备知识我们就可以来看下KMP算法的思想到底是怎样的了。请看下面这个例子：

图4 改进的字符匹配方法示意

读者看到这里可以先留一个最初的印象，改进的字符串匹配算法确实减少了匹配的次数。如果采用i回溯的方式，也就是本节（1）中讲的那种“暴力匹配”的方式需要匹配6次，读者可以自行画图看一下。

从图4我们可以直观的看出，每次重新匹配的时候，i并没有回溯，而是在主串上一次匹配失败的位置，与模式串的某一位置重新进行匹配。

那么，KMP算法就可以描述成这样：在匹配过程中产生“失配”（即图4中红框圈出的部分）时，主串中的当前“失配”的位置（i）应该与模式串中的哪个位置再进行接下来的比较，假设这个位置记作k，用一个函数的函数值next[j] = k来表示：当模式串中的第j个字符与主串当前位置i的字符“失配”时，next[j]的值就是重新要和当前主串i位置上的字符进行对比的模式串字符的位置。（这句话有点绕，笔者已经尽可能以容易理解的文字进行描述了，如看不懂请多读几遍，或者多看几遍图3，相信聪明的读者会想明白）

那么重点就来了，只要得到了next函数，就能知道下次重新匹配的时候从模式串哪个位置开始进行匹配。假设主串为's1s2...sn'，模式串为'p1p2...pm'，在主串与模式串匹配过程中某一位置“失配”（si ≠ pj），假设此时主串i位置的字符与模式串k（k < j）位置的字符继续进行比较，通过图4看出，k之前的字符主串与模式串中的是相等的，那么则满足以下等式：

图5 部分匹配示意

next函数的定义：

图6 next函数定义

由上述定义可以得出如下模式串对应的next函数值：

不过，这样的话，是不是next函数算起来也有点绕，一不小心就算错了，那么我们可以根据这个定义用递推方法求得next函数值。

首先我们根据上述表格看出，next函数的函数值取决于模式串本身与主串没有关系（划重点）。

推导过程如下：

图7 next函数推导

根据上述推导，代码如下：

void GetNext(SString T,int next[])
{
    int i = 1;
    int 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];
        }
    }
} 

有了next函数，可以将之前“暴力匹配”的代码修改一下，让其在匹配不成功之后，j的位置移向next[j]，而i则不用再回溯。

int IndexKMP(SString S,SString T,int pos)
{
    int i,j;
    i = pos;    /* 主串开始比对位置 */
    j = 1;

    while((i <= S.length) && (j <= T.length))
    {
        if(S.ch[i - 1] == T.ch[j - 1])
        {
            /* 继续比较后续字符 */
            i ++;
            j ++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if(j > T.length)
    {
        return (i - T.length);
    }
    else
    {
        return (-1);
    }
}

KMP算法对于庞大的字符文件很有效，如果字符数目不多的话，其实和“暴力匹配”的方法时间复杂度上差距不大。以上均为笔者自己的理解，如有错误欢迎指正 。

参考资料：《数据结构》 严蔚敏 吴伟民 著