数据结构之串

数据结构与算法

一、串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。
串一般记为$s="a_1a_2......a_n"(n≥0)$。s是串的名称，用双引号或单引号括起来的字符序列是串的值（引号不属于串的内容）。$a_i（1≤i≤n）$可以是字母、数字或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，n是一个有限的数值。零个字符的串称为空串（nullstring），它的长度为零，可以直接用两双引号“""”表示，也可以用希腊字母“Φ”来表示。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。
几种特殊的串
空格串：只包含空格的串。
子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。子串在主串中的位置就是子串的第一个字符在主串中的序号。

二、串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
目前计算机常用的编码方式为标准的ASCII编码，由7位二进制数表示一个字符，总共可以表示128个字符。后来发现一些特殊符号的出现，128个不够用，于是扩展ASCII码由8位二进制数表示一个字符，总共可以表示256个字符，这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。
全世界有成百上千种语言与文字，显然这256个字符是不够的，因此后来就有了Unicode编码，比较常用的是由16位的二进制数表示一个字符，这样总共就可以表示$2^{16}$个字符，约是6.5万多个字符，足够表示世界上所有语言的所有字符了。为了和ASCII码兼容，Unicode的前256个字符与ASCII码完全相同。
$给定两个串：s="a_1a_2......a_n"，t="b_1b_2......b_m"，\\当且仅当n=m，且a_1=b_1，a_2=b_2，……，a_n=b_m时，则认为s=t。$

三、串的抽象数据类型

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

不同的高级语言，对串的基本操作会有不同的定义方法。
操作Index的实现算法

/* T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0 */
int Index(String S, String T, int pos)
{
    int n, m, i;
    String sub;
    if (pos > 0)
    {
        /* 得到主串S的长度 */
        n = StrLength(S);                   
        /* 得到子串T的长度 */
        m = StrLength(T);                   
        i = pos;
        while (i <= n - m + 1)
        {
            /* 取主串第i个位置 */
            /* 长度与T相等子串给sub */
            SubString(sub, S, i, m);        
            /* 如果两串不相等 */
            if (StrCompare(sub, T) != 0)    
                ++i;
            /* 如果两串相等 */
            else                            
                /* 则返回i值 */
                return i;                   
        }
    }
    /* 若无子串与T相等，返回0 */
    return 0;                               
}

四、串的存储结构

4.1 串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

定长数组存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，也可以是在存储数组的最后一个下标位置。“\0”来表示串值的终结。
但是这样定长数组存储串是很有问题的，串的两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度Max-Size。于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

4.2 串的链式存储结构

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

这样的话，一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。

串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

五、模式匹配算法

5.1 朴素的模式匹配算法

朴素的模式匹配算法：对主串(S)的每一个字符作为子串(T)开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。
实现代码如下：

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

最坏时间复杂度：O((n-m＋1)*m)。
比如主串S="00000000000000000000000000000000000000000000000001"，而要匹配的子串为T="0000000001"，如图：

直到最后第41个位置，因为全部匹配相等，所以不需要再继续进行下去：

这种算法效率非常差！

5.2 KMP模式匹配算法

KMP算法：全称“克努特—莫里斯—普拉特算法”。
下面具体介绍KMP算法的原理：
考虑主串S="abcdefgab"，要匹配的子串T="abcdex"，如果用朴素算法的话：

朴素算法是①②③④⑤⑥，但是很明显，对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于①来说，前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位的字符相等。所以②③④⑤的判断都是多余，只保留①⑥即可。

注意 ：T串中首字符“a”与T中后面的字符均不相等是前提。

考虑到T中有重复字母的情况：

S="abcababca"，T="abcabx"，步骤②③都是多余，④⑤这两个比较得出字符相等的步骤也可以省略。

在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的。而通过分析可以发现，这种回溯其实是可以不需要的，KMP模式匹配算法就是为了让这没必要的回溯不发生。

把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。于是可以得到下面的函数定义：

5.2.1 next数组值推导

1．S="abcdefgab", T="abcdex"：

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）以后同理，所以最终此T串的next[j]为011111。

2．S="abcdefgab", T="abcabx"：

1）当j=1时，next[1]=0；
2）当j=2时，同上例说明，next[2]=1；
3）当j=3时，同上，next[3]=1；
4）当j=4时，同上，next[4]=1；
5）当j=5时，此时j由1到j-1的串是“abca”，前缀字符“a”与后缀字符“a”相等（前缀用下划线表示，
后缀用斜体表示），因此可推算出k值为2（由‘p1...pk-1’=‘pj-k＋1...pj-1’，得到p1=p4）因此next[5]=2；
6）当j=6时，j由1到j-1的串是“abcab”，由于前缀字符“ab”与后缀“ab”相等，所以next[6]=3。
根据经验得到如果前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值就是n+1。

2．S="abcdefgab", T="ababaaaba"：

1）当j=1时，next[1]=0；
2）当j=2时，同上next[2]=1；
3）当j=3时，同上next[3]=1；
4）当j=4时，j由1到j-1的串是“aba”，前缀字符“a”与后缀字符“a”相等，next[4]=2；
5）当j=5时，j由1到j-1的串是“abab”，由于前缀字符“ab”与后缀“ab”相等，所以next[5]=3；
6）当j=6时，j由1到j-1的串是“ababa”，由于前缀字符“aba”与后缀“aba”相等，所以next[6]=4；
7）当j=7时，j由1到j-1的串是“ababaa”，由于前缀字符“ab”与后缀“aa”并不相等，只有“a”相等，
所以next[7]=2；
8）当j=8时，j由1到j-1的串是“ababaaa”，只有“a”相等，所以next[8]=2；
9）当j=9时，j由1到j-1的串是“ababaaab”，由于前缀字符“ab”与后缀“ab”相等，所以next[9]=3。

5.2.2 KMP模式匹配算法实现

通过以上分析，可以写出代码：

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

计算出当前要匹配的串T的next数组代码：

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

对于get_next函数来说，若T的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值的不回溯，使得index_KMP算法效率得到了提高，while循环的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(n＋m)
KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显。

5.3 KMP模式匹配算法改进

KMP还是有缺陷的: 如果主串S="aaaabcde"，子串T="aaaaax"，其next数组值分别为012345，在开始时，当i=5、j=5时，我们发现“b”与“a”不相等，如图①，因此j=next[5]=4，如图中的②，此时“b”与第4位置的“a”依然不等，j=next[4]=3，如图中的③，后依次是④⑤，直到j=next[1]=0时，根据算法，此时i++、j++，得到i=6、j=1，如图中的⑥。

上图的②③④⑤步骤，其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的“a”相等，那么可以用首位next1的值去取代与它相等的字符后续next[j]的值。

假设取代的数组为nextval，改进代码如下：

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

际匹配算法，只需要将“get_next(T,next);”改为“get_nextval(T,next);”即可。

5.3.1 nextval数组值推导

改良后的nextval与next值完全不同了，比如：
1．T="ababaaaba"

先算出next数组的值分别为011234223，然后再分别判断。
1）当j=1时，nextval[1]=0；
2）当j=2时，因第二位字符“b”的next值是1，而第一位就是“a”，它们不相等，所以nextval[2]=next[2]=1，维持原值。
3）当j=3时，因为第三位字符“a”的next值为1，所以与第一位的“a”比较得知它们相等，所以nextval[3]=nextval[1]=0；
4）当j=4时，第四位的字符“b”next值为2，所以与第二位的“b”相比较得到结果是相等，因此nextval[4]=nextval[2]=1；
5）当j=5时，next值为3，第五个字符“a”与第三个字符“a”相等，因此nextval[5]=nextval[3]=0；
6）当j=6时，next值为4，第六个字符“a”与第四个字符“b”不相等，因此nextval[6]=4；
7）当j=7时，next值为2，第七个字符“a”与第二个字符“b”不相等，因此nextval[7]=2；
8）当j=8时，next值为2，第八个字符“b”与第二个字符“b”相等，因此nextval[8]=nextval[2]=1；
9）当j=9时，next值为3，第九个字符“a”与第三个字符“a”相等，因此nextval[9]=nextval[3]=0。

2．T="aaaaaaaab"

1）当j=1时，nextval[1]=0；
2）当j=2时，next值为1，第二个字符与第一个字符相等，所以nextval[2]=nextval[1]=0；
3）同样的道理，其后都为0……；
4）当j=9时，next值为8，第九个字符“b”与第八个字符“a”不相等，所以nextval[9]=8。

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