5.1-5.2 串的定义

串(string)是由零个或多个字符组成的有限序列，又名叫字符串。
一般记为s=“a1a2……an”(n>0)，其中，s是串的名称，用双引号(有些书中也用单引号)括起来的字符序列是串的值，注意单引号不属于串的内容。ai(1≤i≤n)可以是字母、数字或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，定义中谈到“有限”是指长度n是一个有限的数值。零个字符的串称为空串(null string)，它的长度为零，可以直接用两双引号“”””表示，也可以用希腊字母“Φ”来表示。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。

还有一些概念需要解释：

• 空格串，是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。
• 子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
• 子串在主串中的位置就是子串的第一个字符在主串中的序号。

开头我所提到的“over”、“end”、“lie”其实可以认为是“over”、“friend”、“believe”这些单词字符串的子串。

5.3 串的比较

两个字符串的长度以及它们每个位置各个对应位置的字符都相等时，才算是相等。
那么对于两个串不相等时，如何判定它们的大小呢。我们这样定义：
给定两个串：s=“a1a2……an”，t=“b1b2……bm”，当满足以下条件之一时，s<t。

1. n<m，且ai=bi(i=1，2，…，n)。
   例如当s=“hap”，t=“happy”，就有sst。因为t比s多出了两个字母。
2. 存在某个k<min(m，n)，使得ai=bi；(i=1，2，……，k-1)，ak<bk。
   例如当s=“happen”，t=“happy”，因为两串的前4个子母均相同，间内串第5个字母(k值)，字母e的ASCII码是101，而字母y的ASCII码是121，显然e<y，所以s<t。

5.4 串的抽象数据类型

ADT 串(string)
Data
  串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
  strAssign(T，*chars)：生成一个其值等于字符串常量chars的串T。
  StrCopy(T，S)：串S存在，由串S复制得串T。
  ClearString(S)：串S存在，将串清空。
  StringEmpty(S)；若串S为空，返回true，否则返回false。
  StrLength(S)：返回串S的元素个数，即串的长度。
  StrCompare(S，T)：若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0。
  Concat(T，S1，S2)：用T返回由S1和S2联接而成的新串。
  SubString(Sub，S，pos，len)：串S存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1，用Sub返回串S的第pos个字符起长度为len的子串。
  Index(S，T，pos)：串S和T存在，T是非空串，1≤pos≤StrLength(S)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0。
  Replace(S，T，V)：串S、T和v存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。
  StrInsert(S，pos，T)：串s和T存在，1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。
  StrDelete(S，pos，len)：串S存在，1≤pos≤StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT

5.5 串的存储结构

串的存储结构与线性表相同，分为两种。

5.5.1 串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。
既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了，其实这还是需要占用一个空间，何必呢。

5.5.2 串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全，如图5-5-3所示。

当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。
但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

5.6 朴素的模式匹配算法(暴力算法匹配)

子串的定位操作通常称做串的模式匹配，也算是串中最重要的操作之一。
用基本的数组来实现朴素的模式匹配算法。我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。实现代码如下：

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(String S, String T, int pos)
{
    int i = pos;    /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    int j = 1;                /* j用于子串T中当前位置下标值 */
    while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    {
        if (S[i] == T[j])     /* 两字母相等则继续 */
          {
            ++i;
            ++j;
          }
          else                 /* 指针后退重新开始匹配 */
          {  
             i = i-j+2;        /* i退回到上次匹配首位的下一位 */
             j = 1;             /* j退回到子串T的首位 */
          }
    }
    if (j > T[0])
        return i-T[0];
    else
        return 0;
}

非最坏情况下，只需要匹配2个串的首字母，所以根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。
而最坏情况就是0000000000000000001，此时时间复杂度为O((n-m+1)*m)。

5.7 KMP 模式匹配算法

有三位前辈，D.E.Knuth、J.H.Morris 和V.R.Pratt（其中Knuth和Pratt 共同研究，Morris独立研究）发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特一莫里斯一普拉特算法，简称KMP算法。

5.7.1 KMP模式匹配算法原理

首先要理解上面的朴素模式的匹配算法，主串设为S，要匹配的模式串设为T。
对于在子串中有与首字符相等的字符，也是可以省略一部分不必要的判断步骤。
我们在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的。而我们的分析发现，这种回溯其实是可以不需要的，我们的KMP模式匹配算法就是为了让这没必要的回溯不发生。
既然i值不回溯，也就是不可以变小，那么要考虑的变化就是j(j在模式串中所在的位置)值了。通过观察也可发现，我们屡屡提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j(j在模式串中所在的位置)值的变化就会不相同。也就是说，这个j(j在模式串中所在的位置)值的变化与主串其实没什么关系，关键就取决于T串的结构中是否有重复的问题。
我们可以得出规律，j(j在模式串中所在的位置)值的多少取决于当前字符之前的串的前后缀的相似度。
我们把T串各个位置的j(j在模式串中所在的位置)值的变化定义为一个数组next，那么next的长度就是T串的长度。于是我们可以得到下面的函数定义：

5.7.2 next数组值推导

“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；
“后缀”指除了第一个字符以外，一个字符串的全部尾部组合。
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

• “A”的前缀和后缀都为空集，共有元素的长度为0；
• “AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
• “ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
• “ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
• “ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
• “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
• “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

我们可以根据经验得到:如果前缀后缀最长共有元素的长度为1，k值是2，最长的共有元素的长度为2，k值是3。
最长的共有元素的长度为n，k值就是n+1。

5.7.3KMP模式匹配算法实现

next代码如下：

/* 通过计算返回子串T的next数组。 */
void get_next(String T, int *next)
{
    int i, j;
    i = 1;
    j = 0;
    next[1] = 0;
    while (i < T[0])  /* 此处T[0]表示串T的长度 */
    {
        if (j == 0 || T[i] == T[j])     /* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];    /* 若字符不相同，则j值回溯 */
    }
}

这段代码的目的就是为了计算出当前要匹配的串T的next数组。

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
/*  T非空，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos)
{
    int i = pos;        /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    int j = 1;            /* j用于子串T中当前位置下标值 */
    int next[255];        /* 定义一next数组 */
    get_next(T, next);    /* 对串T作分析，得到next数组 */
    while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    {
        if (j == 0 || S[i] == T[j])     /* 两字母相等则继续，与朴素算法增加了j=0判断 */
        {
            ++i;
            ++j;
        }
        else             /* 指针后退重新开始匹配 */
            j = next[j];/* j退回合适的位置，i值不变 */
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

对于get_next函数来说，若模式串的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值的不回溯，使得indexKMP算法效率得到了提高，while 循环的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(n+m)。相较于朴素模式匹配算法的O((n-m+1)*m)来说，是要好一些。

5.7.4 KMP模式匹配算法改进

/* 求模式串T的next函数修正值并存入数组nextval */
void get_nextval(String T, int *nextval)
{
    int i, j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0])  /* 此处T[0]表示串T的长度 */
    {
        if (j == 0 || T[i] == T[j])     /* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
        {
            ++i;
            ++j;
            if (T[i] != T[j])      /* 若当前字符与前缀字符不同 */
                nextval[i] = j;    /* 则当前的j为nextval在i位置的值 */
            else
                nextval[i] = nextval[j];    /* 如果与前缀字符相同，则将前缀字符的 */
                                            /* nextval值赋值给nextval在i位置的值 */
        }
        else
            j = nextval[j];            /* 若字符不相同，则j值回溯 */
    }
}

5.7.5 nextval 数组值推导

总结改进过的KMP算法，它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next的值。

5.8 总结回顾

这一章节我们重点讲了“串”这样的数据结构，串（string）是由零个或多个字符组成的有限序列，又名叫字符串。本质上，它是一种线性表的扩展，但相对于线性表关注一个个元素来说，我们对串这种结构更多的是关注它子串的应用问题，如查找、替换等操作。现在的高级语言都有针对串的函数可以调用。我们在使用这些函数的时候，同时也应该要理解它当中的原理，以便于在碰到复杂的问题时，可以更加灵活的使用，比如KMP模式匹配算法的学习，就是更有效地去理解index函数当中的实现细节。