Fabian备忘录

人类资格证考核中

四、串

发表于 更新于 分类于 ，
本文字数： 4.9k

串的定义和实现

串，即字符串是由零个或多个字符组成的有限序列，一般记为。其中S是串命，n为串的长度

  • n=0时的串被称为空串(用表示)
  • 子串：串中任意个连续字符组成的子序列。空串也是字串；
  • 主串：包含子串的串；
  • 字符在主串中的位置称为字符在串中的序号。注意序号是从1开始的；
  • 子串在主串中的位置：子串第一个字符在主串中的位置；

串是一种特殊的线性表，数据元素之间呈现线性关系。串的数据对象限定为字符集。串的基本操作，通常以子串为操作对象。

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
//串的基本操作

//赋值操作，把串T赋值为chars
StrAssign(&T, chars);

//复制操作，由串S复制得到串T
StrCopy(&T, S);

//判空操作
StrEmpty(S);

//求串的长度，返回元素个数
StrLength(S);

//清空操作，将S清为空串
ClearString(&S);

//销毁串，回收存储空间
DestroyString(&S);

//串联接，用T返回由S1和S2联接成的新串
Concat(&t, S1, S2);

//求子串。用Sub返回串S的第pos个字符起长度为len的子串
SubString(&Sub, S, pos, len);

//定位操作。若主串s中存在与串T值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0
Index(S,T);

//比较操作，若S>T，则返回值>0,若S=T，则返回值=0；若S<T，则返回值<0,内部比较的是字符编码
StrCompare(S, T);

串的存储结构

串是特殊的线性表，所以参考线性表的存储方式来存储。

顺序存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define MAXLEN 255

//定长顺序存储
typedef struct{
    char ch[MAXLEN];   //每个分量存储一个字符
    int length;        //串的实际长度
}SString;


//堆分配存储
typedef struct{
    char *ch;     //按串长分配存储区，ch指向串的基地址
    int length;   //串的长度
}HString;
HString S;
S.ch = (char*)malloc(MAXLEN * sizeof(char));
S.length = 0;

char ch[10]有四种存储方式

  1. 数组+变量length;
  2. 不设置length变量，ch[0]充当length，这样做可以保证字符的位序和数组下标相同
  3. 没有length变量，以字符'\0'表示结尾
  4. 设置变量length，并且ch[0]弃用。后续都用这个方式表示
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
38
39
40
41
42
43
typedef struct{
    char ch[MAXLEN];   //每个分量存储一个字符
    int length;        //串的实际长度
}SString;

bool SubString(SString &Sub, SString S, int pos, int len)
{
    //判断子串范围是否越界
    if(pos + len - 1 > S.length)
        return false;

    for(int i = pos, i < pos+len; i++)
    {
        Sub.ch[i-pos+1] = S.ch[i];
    }
    Sub.length = len;
    return true;
}

int StrCompare(SString S, SString T)
{
    for(int i = 1; i <= S.length && i <= T.length; i++)
    {
        if(S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }

    //扫描过的所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

int Index(SString S, SString T)
{
    int i = 1, n = StringLength(S), m = StrLength(T);
    SString sub;  //用于暂存子串
    while(i <= n-m+1)
    {
        SubString(sub, S, i, m);
        if(StrCompare(sub, T) != 0) ++i;
        else return i;   //返回子串在主串中的位置
    }
    return 0; //S中不存在与T相等的子串
}

链式存储

1
2
3
4
typedef struct StringNode{
    char ch;    //每个结点存一个字符
    struct StringNode *next;
}StringNode, *String;

上面的做法存储密度很低，因为每个字符只占1B，但每个指针占用4B，有效信息占比太低，所以可以选择下面的方法存储：

1
2
3
4
typedef struct StringNode{
    char ch[4];         //每个结点存多个字符
    struct StringNode *next;
}StringNode, *String;

串的模式匹配

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置。

朴素模式匹配算法

朴素模式匹配算法其实就是暴力匹配。

主串长度为n，模式串长度为m；将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或者所有子串都不匹配为止。

主串长度为n，模式串长度为m，则最多比较n-m+1个子串。

基础操作Index定位操作，其实就是朴素模式匹配算法：

1
2
3
4
5
6
7
8
9
10
11
12
int Index(SString S, SString T)
{
    int i = 1, n = StringLength(S), m = StrLength(T);
    SString sub;  //用于暂存子串
    while(i <= n-m+1)
    {
        SubString(sub, S, i, m);
        if(StrCompare(sub, T) != 0) ++i;
        else return i;   //返回子串在主串中的位置
    }
    return 0; //S中不存在与T相等的子串
}

 

也可以不使用字符串的基本操作，直接通过数组下标实现朴素模式匹配算法：

  1. 变量i代表主串的数组下标，变量j代表模式串的数组下标
  2. 依次对比主串和子串对应的值，如果字符相等，i++,j++；
  3. 若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置;
  4. 若j>T.length，则当前子串匹配成功，返回当前子串第一个字符的位置--i-T.length;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Index(SString S, SString T)
{
    int i = 1; j = 1;
    while(i <= S.length && j <= T.length){
        if(S.ch[i] == T.ch[i]){
            //继续比较后续字符
            ++i;
            ++j;
        }
        else{
            //指针退后重新匹配
            i = i - j +2;
            j = 1;
        }
    }
    if(j > T.length)
        return i - T.length;
    else 
        return 0;
}

设主串长度n，子串长度m，则：

  • 最坏时间复杂度---模式串全部遍历完才能发现不匹配，遍历到主串末尾
  • 平均时间复杂度

KMP算法

基于朴素模式匹配算法优化得来的。朴素模式匹配算法中，依次遍历主串和模式串，一旦遍历失败，那么指针回溯，一切从头开始匹配。

但其实某一个子串哪怕匹配失败，但前面已经匹配过的字符是我们完全已知的，相当于模式串的子串。我们可以不用回溯主串指针。

以模式串"abaabc"为例：

上图主串S和模式串匹配到第6个元素的时候，由于前5个元素已经知道了，那么可以令主串指针不变，依旧指向第6位，模式串直接从第3位开始匹配。依次类推。

这种匹配方式和主串无关，只和模式串有关，例如针对模式串T="abaabc"，有：

  • 当第6个元素匹配失败时，可令主串指针i不变，模式串指针j=3;
  • 当第5个元素匹配失败时，可令主串指针i不变，模式串指针j=2;
  • 当第4个元素匹配失败时，可令主串指针i不变，模式串指针j=2;
  • 当第3个元素匹配失败时，可令主串指针i不变，模式串指针j=1;
  • 当第2个元素匹配失败时，可令主串指针i不变，模式串指针j=1;
  • 当第1个元素匹配失败时，匹配下一个相邻子串，令j=0，i++,j++;

这样我们可以得到一个next数组：

next[0] next[1] next[2] next[3] next[4] next[5] next[6]
0 1 1 2 2 3

改造朴素模式匹配算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Index_KMP(SString S, SString T, int next[])
{
    int i = 1, j = 1;
    while(i <= s.length && j <=T.length)
    {
        if(j == 0 || S.ch[i] == T.ch[j]){
            //继续匹配后继字符
            ++i;
            ++j;
        }
        else
            j = next[j];   //模式串向右移动
    }

    if(j > T.length)
        return i-T.length;   //匹配成功
    else
        return 0;
}

KMP算法的最坏时间复杂度为;其中求next数组的时间复杂度，模式匹配过程最坏复杂度；

next数组手算

next数组作用：当模式串第j个字符匹配失败时，从模式串的第next[j]开始继续往后匹配；

任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串，因此next[1]无脑写0；

任何模式串都一样，第二个字符不匹配时，应尝试匹配模式串的第1个字符，因此next[2]无脑写1；

在不匹配的位置前画分界线，模式串一步步后退，直到分界线之前完全“能对上”，或者模式串完全跨过分界线为止。此时j指向哪里，next数组值就是多少

nextval数组

next数组的思路，其中中间有很多不必要的步骤，以模式串"abaabc"为例，next[3]=1，也就是当第三个字符不匹配时，模式串回溯到第一个位置去匹配，可是模式串第三个字符和第一个字符都是a，再次匹配依旧匹配不上，所以我们可以直接从头开始。以此类推next[5]=2,可是模式串第五个字符和第二个字符都是'b',从第二个字符开始依旧匹配不上，所以可以从next[2]开始匹配，即从1开始匹配。

手算解题：先求next数组，再由next数组求nextval数组：

1
2
3
4
5
6
7
8
nextval[1] = 0;

for(int j = 2; j <= T.length; j++){
    if(T.ch[next[j]] == T.ch[j])
        nextval[j] = nextval[next[j]];
    else
        nextval[j] = next[j];
}
序号j next[1] next[2] next[3] next[4] next[5] next[6]
模式串 a b a b a a
next[j] 0 1 1 2 3 4
nextval[j] 0 1 0 1 0 4

代码计算next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void get_next(String T, int next[])
{
    int 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];
    }
}