串

串的定义及基本操作

串的定义

以下是串的相关概念

• 串，即字符串是由0个或多个字符组成的有限序列。一般记为$S=“a_1{a}_2\cdot \cdot \cdot a_n”(n\ge 0)$
• 串名
• 串的值
• 串的长度
• 空串（用$\varnothing$表示）
• 子串，串中任意个连续的字符组成的子序列
• 主串，包含子串的串
• 字符在主串中的位置，字符在串中的序号，没说一般默认为第一次出现的位置。

注意位序从1开始而不是从0开始

• 子串在主串中的位置，子串的第一个字符在主串中的位置

串与线性表

串是一种特殊的线性表。串的数据对象限定为字符集（如中文字符，英文字符，数字字符，标点字符等）。但是相比线性表，串的基本操作一般以子串为操作对象。

串的基本操作

比较操作中，从第一个字符开始往后依次对比，先出现更大字符的串就更大。长串的前缀与短串相同时，长串更大。只有两个串完全相同时，才相等

串的存储结构

串的顺序存储

• 静态数组实现（定长顺序存储）

#define MAXLEN 255     //预定义最大串长为255
typedef struct{
    char ch[MAXLEN];   //每个分量存储一个字符
    int length;        //串的实际长度
}SString;
1
2
3
4
5

• 动态数组实现（堆分配存储）

typedef struct{
    char *ch;        //按串长分配空间，ch指向串的基地址
    int length;      //串的长度
}HString; 

HString S;
S.ch=(char*)malloc(MAXLEN*sizeof(char));
S.length=0;
1
2
3
4
5
6
7
8

malloc函数所申请的内存空间属于内存里的堆区，所以这种实现方式被称为堆分配存储（其实就是个动态数组），堆区的这片内存空间需要手动free回收

不同教材里顺序存储实现的细节会有些不同，优缺点也不同

方案一是我们刚才提到的方案，即申请一个数组并有专门的一个int类型变量记录字符串长度

方案二的优点是字符的位序和数组下标相同。缺点是由于数组是char型的，因此字符串的长度要被限制在255以内，否则char[0]表示不了那么多的数字。

方案三不记录串的长度，而是在串的末尾处插入特殊字符’\0’（对应ASCII码的0）。这种方案的缺点是想要知道串的长度需要从头到尾进行遍历

方案四是教材的方案。即舍弃char[0]不用，设置额外的int类型变量来记录字符串的长度，之后的讲解也默认采用这种方案

串的链式存储

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

这种存储方式每个字符占1B，每个指针4B（32位下），存储密度较低。因此可以适当改进，让存储密度提高

typedef struct StringNode{
    char ch[4];                //每个结点存多个字符，没有字符的位置用'#'或'\0'补足
    struct StringNode *next;
}StringNode,*String;
1
2
3
4

基本操作的实现(基于静态数组)

StrLength(S)函数求串长直接返回length，ClearString(&S)函数清空操作把length值置为0即可

求子串

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

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.lengrh=len;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11

比较操作

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S

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;
}
1
2
3
4
5
6
7
8
9

定位操作

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

int Index(SString S,SString T){
    int i=1,n=StrLength(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
5
6
7
8
9
10
11
12
13

串的朴素模式匹配算法

上一节的定位操作用基本操作实现串的模式匹配，这一节则是尝试不使用其他的基本操作，直接访问数组元素来实现该串的模式匹配

朴素模式匹配算法

int Index(SString S,SString T){
    int k=1;
    int i=k,j=1;
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;       //继续比较后续字符
        }else{
            k++;       //检查下一个子串
            i=k;
            j=1;
        }
    }
    if(j>T.length){
        return k;
    }else{
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

课本的代码实现略有不同，这里略过

朴素模式匹配算法性能分析

设模式串长度为$m$，主串长度为$n$，则

• 匹配成功的最好时间复杂度：$O(m)$

第一次匹配就成功

• 匹配失败的最好时间复杂度：$O(n)$

全部匹配失败且每个子串的第$1$个个字符就与模式串不匹配。要匹配$n-m+1$次（主串内有$n-m+1$个长度为$m$的子串，都要依次匹配），时间复杂度为$O(n-m+1)=O(n-m)$,考虑到许多情况下主串长度远大于模式串长度，时间复杂度可进一步约等于$O（n）$

• 最坏时间复杂度：$O（mn）$

每个子串的前$m-1$个字符都和模式串匹配，只有第$m$个字符不匹配。匹配成功/匹配失败最多需要$（n-m+1）\times m$次比较。

KMP算法(一)

观察上一节的朴素模式匹配算法，朴素模式匹配算法中设置了两个指针$i,j$，一个指向主串元素，一个指向模式串元素，通过移动指针$i,j$并比较指针$i,j$各自指向的元素是否相等来寻找子串。不难发现朴素模式匹配算法的缺点在于当某些子串与模式串能部分匹配但是匹配失败时，主串的扫描制针$i$要回溯，造成时间开销增大。因此KMP算法的改进思路是当子串和模式串不匹配时，主串指针$i$尽量不回溯，让模式串指针$j$回溯

那么模式串指针应该回溯到哪儿呢？

如果$j=k$时才发现匹配失败，说明$1\sim k-1$都匹配成功。可以设置一个$next$数组决定当模式串指针$j$等于某个$k$时发生不匹配模式串指针$j$应该回溯到哪儿（即$j=k$且发现字符不匹配时令$j=next[k]$）。$KMP$算法的关键就在于做出一个和模式串相对应的数组$next$

这里可以这样理解，假设模式串为”$ababaa$“，若$i=8,j=5$时发生不匹配，则说明主串$i=4\sim 7$部分和模式串$j=1\sim 4$部分的字符均为”$abab$“。从模式串开头和末尾各取相同个数的元素观察相似情况，发现模式串开头$j=1\sim 2$部分和末尾$j=3\sim 4$部分完全相同均为”$ab$“，而且再多取元素都不能做到完全相同。由于最长相同部分的长度为2，所以保持$i$不动，$j$回溯到$j=2+1=3$的位置判断$i=8,j=3$时是否匹配，这样能保证主串$i=6\sim 7$部分和模式串$j=1\sim 2$部分 均为”$ab$“相匹配

下图就是模式串为$google$时的情况，根据手动算出的$next$数组决定不同情况下指针$j$应该回到哪儿，手算$next$数组的具体公式下节会给出

$j=1$时发现不匹配则令$j=next[1]=0$，这样设计是为了方便下面的代码实现。如果把$next[1]$设为$0$，我们就可以利用这个设计做一个特殊的判断，当$j=0$时就说明主串的指针$i$应该往右移动了，而其他情况下发生不匹配都只移动模式串指针$j$。在这种情况下我们可以先令$j=0$，再让$i$和$j$都同时$++$，这样就能让指针$i$往后移一位，同时$j$也保持为$1$，下面的代码就体现了这种思想

KMP算法代码

int Index_KMP(SSting S,SSting 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMP算法(二)

这一节主要探讨应该怎么求$next$数组

求模式串的next数组

先引入两个定义

• 串的前缀：包含第一个字符，且不包含最后一个字符的子串
• 串的后缀：包含最后一个字符，且不包含第一个字符的子串

next数组的手算方法

当$j$个字符匹配失败，由前$1\sim j-1$个字符组成的串记为$S$，则：$next[j]=S$的最长相等前后缀长度$+1$。特别地，$next[1]=0$

以$goole$为例，当第$4$个字符匹配失败，取前$1\sim 3$个字符组成的串$S(goo)$，观察串$goo$，取其长度为$1,2$的前缀分别为长度为$1,2$的后缀进行比较，因为都不相等，所以$S$的最长相等前后缀长度为$0$，故$next[j]=1$

其实再分析一下可以发现$next[2]=1$也是可以确定的

上述结论可以总结为

代码实现

//求模式串T的next数组
void get_next(SString 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++;  
            //若pi=pj,则next[j+1]=next[j]+1
            next[i]=j;
        }else{
            //否则令j=next[j]，循环继续
            j=next[j];
        }
    }
}

//KMP算法
int Index_KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);                 //求模式串的next数组，时间复杂度O(m)
    while(i<=S.length&&j<=T.length){  //时间复杂度O(n)
        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;
    }
}
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

上课的时候没讲求$next$数组的代码实现原理，只讲了如何手算$next$数组。代码实现的原理可以看下文

https://www.cnblogs.com/ciyeer/p/9035072.html

KMP算法平均时间复杂度：$O（m+n）$

如果不会经常出现子串与模式串部分匹配问题，那么$KMP$算法的优势并没有那么明显

KMP算法的进一步优化

可以在之前基础上用$nextval$数组替换$next$数组，当子串和模式串不匹配时令$j=nextval[j]$来进一步减少无意义的对比

以模式串$google$为例，当$j=4$时发生不匹配（此时指针$j$指向字符$g$），根据算出的$next$数组令$j=next[j]=1$，按照之前提供的步骤此时应该继续对比模式串$goole$的第$1$个字符与指针$i$指向的字符看是否相等，但我们可以提前知道模式串的第$1$个字符与第$4$个字符都是$g$，当前检查的主串字符如果与第$4$个字符不匹配的话就肯定和第$1$个也不匹配，所以当第$4$个字符匹配失败的时候应直接让$j$等于和$next[1]$相同的值

nextval数组的具体求法

下面以模式串${}^{\prime }ababa{a}^{\prime }$为例演示已知$next$数组怎么求对应的$nextval$数组

首先$j=1$时，$nextval[1]=0$可以直接写上

再往下看$j=2$的情况。$next[2]=1$，当$j=1$时模式串对应字符为$a$，而$j=2$时模式串对应字符为$b$，二者不相等。故$nextval[2]=next[2]=1$

再往下看$j=3$的情况。$next[3]=1$，当$j=1$时模式串对应字符为$a$，而$j=3$时模式串对应字符为$a$，二者相等。故$nextval[3]=next[1]=0$

再往下看$j=4$的情况。$next[4]=2$，当$j=2$时模式串对应字符为$b$，而$j=4$时模式串对应字符为$b$，二者相等。故$nextval[4]=next[2]=1$

接下来的类比以上过程即可求得完整的$nextval$数组

代码实现

先算出$next$数组

令$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];
    }
}
1
2
3
4
5
6
7