大话数据结构6-串

发表于 更新于 分类于 ， Valine：

串（string）又称为字符串，字符串的查找匹配等操作在计算机中非常重要，因此将其单独列出来讲解。

I 定义

串（string）是由零个或多个字符组成的有限序列，又名字符串。

一般记为：s="a1a2...an", 其中 s 是串的名称，其中 ai可以是字母、数字或其他字符。串中字符的数目称n为串的长度，零个字符的串称为空串（null string）。

串的大小的比较 可以定义为串中字符对应的编码的大小的比较。常用的编码有：

  • ASCII 编码，8位二进制数表示1个字符，一共可以表示256个。
  • Unicode 编码，16位2进制数表示一个字符，一共可以表示 65万($2^{16}$) 多个字符。

II 串的抽象数据类型

通过抽象数据类型，我们定义串的常用属性和方法，常用的方法包括：

1
2
3
4
5
//生成串，复制串，清空串；
Concat(T,S1,S2);      //用 T 返回由 S1 与 S2 联接而成的新串。
Index(S,T,pos);     //串 S 为主串，返回子串T在主串中的位置(pos位置之后)，如果没有，返回空
SubString(Sub, S, pos, len);    //用sub返回串S的第pos 个字符起长度为len的子串
//等...

这里，我们举一个 Index() 函数的实现例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
T 为非空串。若主串 S 中第 pos 个字符之后存在与 T 相等的子串，
则返回第一个这样的子串在 S 中的位置，否则返回0 
*/
int Index(String S, String T, int pos){
    int n,m,i;
    string sub;

    if(pos > 0){
        n = StrLength(S);       //主串的长度
        m = StrLength(T);       //子串的长度
        i = pos;
        while(i <= n-m+1){      //如果i后面的主串长度大于子串长度，则可能有解
            SubString(sub,S,i,m);      //取主串第i个位置，长度与T相等的子串给sub
            if (StrCompare(sub,T) != 0)     //如果两个串不相等
                ++i;
            else
                return i;
        }
    }
    return 0;       //如果无相等的子串，返回0
}

III 串的模式匹配算法

匹配算法是为了寻找字符串中相同的元素，例如在一篇文章里找一个单词，并统计它的个数。

最直观的方法称为 朴素的模式匹配算法，设主串长度为n，子串长度为m。定义 i（主串的index） 和 j（子串的index），让i从0到遍历到 n-m，子串index不停的从0遍历到m-1。但是这样的做法在最坏的情况下，时间复杂度可以达到 $O(n-m+1)*m$，效率很低.

因此，我们介绍一个更加高效的模式匹配算法，称为 KMP算法（3个人名首字母）。这种算法的核心思想尽量减少重复的比较，主要从两方面进行考虑：

  1. 主串的重复比较。当我们将子串从第一位与主串的第 i 位数开始进行比较，例如直到比较到第 k 位，发现有不同，此时，主串中第 i 到 k 位的值实际上是已知的，即与子串的第 1 到第 (k-i+1) 相同。因此，不再需要比较这些位的字符，主串的“比较指针”（即指定开始比较的第一个值）由 i 变为 k;
  2. 子串的重复比较。
    1. 当子串的首字母与后面字符没有重合时，子串的“比较指针”重新跳到1，与上述的主串的第 k 个字符开始比较。
    2. 当子串的首 n 个字母与子串后部的某 n 个字母相同时，若主串中有与后 n个字母相同的部分（全部or部分，设有t个），需要让子串的比较指针跳转到第t+1 的位置。- (通常，子串会通过一个 next 数组来实现上述功能)总结为，前后缀字符一个相等，k = 2，前后缀字符2个相等，k=3, n个值相等k值就为 n+1.
    3. 当子串中有连续的相等的字母，使用2中的方法也会造成重复判断，若有连续相等的字符，直接用首位的 next[1] 去取代后面的 next[j]. （参考 nextval 的代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//next 数组生成代码
void get_next(string T, int *next){
    int i,j;
    i = 1;
    j = 0;
    next[1] = 0;
    while(i < T[0]){    //T[0]中存放的是字符串的长度
        if(j == 0 || T[i] == T[j]){     //T[i] 表示后缀的单个字符
                                        //T[j] 表示前缀的单个字符
            ++i;
            ++j;
            next[i] = j;
        }else
            j = next[j];        //若字符不相同，则j值回溯
    }     
}

// 返回子串T在主串 S 中第 pos 个字符之后的位置。若不存在，则返回0
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);   //!! 用上面的 next 函数对T进行分析，得到 next 数组
    while(i <= S[0] && j <= T[0]){      //如果i小于S长度，且j小于T的长度，则循环继续
        if(j == 0 || S[i] == T[j]){     //!! 两字母相等则继续比较
            ++i;
            ++j;
        }else{
            j = next[j];      //!! j退回合适的位置，i的值不变
        }
    }
    if(j > T[0])
        return i-T[0];
    else
        return 0;
}

Remark: 上方加叹号的语句认为是较为关键的语句，即相对朴素算法增加的语句。可以分析到，整个代码的时间复杂度最坏情况为 $O(m+n)$。

根据上面对子串的分析第三点，我们编写更新后的 next 程序 nextval 程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 求串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]){
            ++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回溯
    }
}

Remark: KMP 算法确实比较复杂，需要花点时间进一步研究记忆。