数据结构-第三章：串

发表于 更新于 分类于
串。

串的定义和基本操作

串的定义

串，即字符串（String），是由零个或多个字符组成的有限序列。一般记为$S=’a_1a_2…a_n’$。
其中，S是串名，引号内为串值。
如：S=”Hello”
术语：

  • 空串：字符数为0
  • 子串：串中任意个连续的字符组成的子序列。如”ello”是S的子串
  • 主串：包含子串的串。如”HelloWorld”是S的主串
  • 字符在主串中的位置
  • 子串在主串中的位置：子串的第一个字符在主串中的位置

串其实是一种特殊的线性表，只不过：

  • 串的数据对象限定为字符集
  • 串的基本操作通常以子串为操作对象

串的基本操作

两个串大小的比较通过即字典序先后，这里不过多介绍。

串的存储结构

串的顺序存储

静态

1
2
3
4
5
#define MaxLen 10         
typedef struct{
    char ch[MaxLen];
    int length;
}SString;

内存空间系统会自动回收。

动态

1
2
3
4
5
#define MaxLen 10         
typedef struct{
    char *ch;
    int length;
}HString;
1
2
3
4
5
void testString(){
    HSring S;
    S.ch=(char *)malloc(MaxLen*sizeof(char));
    S.length=0;
}

内存空间需要手动回收。

多种实现方式

  • 第二种实现方式的串长不能超过255
  • 第三种实现方式需要遍历才能获得串长

串的链式存储

如果：

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;

如果最后一个结点没有存满，用特殊字符填充。

基本操作的实现

以下基本操作较为简单，不做详细介绍。

求子串

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

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

比较

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

1
2
3
4
5
6
7
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;   //若扫描的字符都相同，则长度长的串更大
}

定位

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

调用前两个方法：

  • 先从主串中依次取出与子串长度相同的子串
  • 比较两个子串是否相等
1
2
3
4
5
6
7
8
9
10
11
12
int Index(SString Sub,SString S){
    int i=0,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;                   //T不是S的子串
}

字符串模式匹配

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

朴素模式匹配算法

设主串长度为n，模式串长度为m。

将主串中所有长度为m的子串（共n-m+1个）依次与模式串对比，直到找到一个完全匹配的子串或所有的子串都不匹配为止。
实际上，使用基本操作中的定位就可以实现。但也可以不使用基本操作，而是直接操作数组下标来实现。

使用两个指针i和j分别指向主串和模式串。

  • 对比指针指向的字符
    • 若相等，二者均后移
    • 若不相等，则i指向下一个子串的第一个位置，j回到模式串第一个位置
      • i=i-j+2（先回到子串前一个位置，再移动到子串下一个位置）
      • j=1
  • 若j>T.length，匹配成功，返回当前子串第一个字符的位置
    • i-T.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Index(SString S,SString T){
    int i=1,j=1
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i;++j;            //继续比较后继字符
        }
        else{
            i=i-j+2;
            j=1;                //指针后退重新匹配
        }
    }
    if(j>T.length)
        return o-T.length;
    else
        return 0;
}

最坏时间复杂度：O(nm)（每个子串都匹配到最后一个字符）

KMP算法

引入

先通过一个例子来引入KMP算法。

对于模式串T如上的模式匹配，假设用朴素模式匹配，其第一次匹配后的结果如下，即模式串中前五个字符均匹配，第六个字符不匹配：

如果继续按照朴素模式匹配，需要从令模式串与主串中的下一个子串匹配。但实际上，主串中不匹配字符之前一定和模式串一致，因此这段子串可视为模式串的一部分。这样可以理解为先令模式串与自身进行一次比较，以避免“冗余”（这个冗余需要仔细品味）的匹配。
这里从第6个字符开始不匹配，因此可以找模式串与其前5个字符最多能匹配多少个。经过简单分析可以知道，模式串与自身第4个字符开始匹配可以满足后续匹配不失误。

什么叫后续匹配不失误呢？举个反例，如果令第模式串与自身第3个字符开始匹配，那么从第四个字符开始匹配就会出现错误。

因此，就可以令主串指针i不变，模式串指针j=3。

假如在另一个主串中，从第4个字符开始不匹配：

那么经过推理可以得知，下次匹配应令主串指针i不变，模式串指针j=2。

如果第从2、3个字符开始失配，也同理可以推出令主串指针不变，只改变模式串指针。

如果第1个元素就匹配失败：

逻辑稍有不同：直接匹配下一个子串，即应令i加一，j不变（仍为1）。为了代码处理方便（见下一小节），先令j=0，然后i与j同时加1。

总结：

  • 其它位元素失配：i不变，改变j指针（改变值只取决于模式串本身，与主串无关，且每一位对应唯一的值）
  • 第1位元素失配：++i，j=1

next数组

定义

由以上分析可知，模式串中每位字符失配后有其对应的j的移动值，且只取决于模式串本身，与主串无关，因此每个字符串就可以对应唯一的数组存储这些移动值。这个数组就称为next数组。

引入中的模式串对应的next数组即为（建议自己推导一下，以便加深理解）：

那么代码大概逻辑就是（这里可以看出为什么会出现j=0：因为第1个元素对应的next值为0）：

这样，主串指针永远不回溯，大大降低了模式匹配的时间复杂度。

求解

next数组的求解不做代码要求，只需手算即可。

  • next[1]永远对应0
  • next[2]永远对应1
  • 在不匹配的为之前，划分界线，模式串一步一步往后退，直到分界线前字符均能匹配或模式串完全跨过分界线位置。此时j指向的位置就是next数组值。

如下图，第5个字符失配，就先在第4第5个字符中间画出分界线：

移动一位，第3位不匹配：

再移动一位，第2位不匹配：

再移动一位，匹配成功，因此next[5]=1：

“google”的next数组为下图，可以推导一遍加深理解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 o-T.length;      //匹配成功
    else
        return 0;
}

最坏时间复杂度:O(m+n)

  • 求next数组O(m)
  • 匹配O(n)

改进

next数组还可以进一步改进，下边通过例子说明。

如下图，对于模式串“abaabc”，其next数组在下图右下角。如果其第3位失配：

说明主串中第3位的值不为“a”，因此j指针指向按next[3]指向第1位。而模式串中的第1位恰恰与第3位的值相等，因此后续匹配（模式串第1位元素与主串第3位元素匹配）必定仍然失败。所以不如直接更新令next[3]=next[1]。

故，可以发现，如果next[x]指向y，而模式串中第x位和第y位的值还想等，应直接令next[x]=next[y]，以避免不必要的匹配。更新后的next数组称为nextval数组。

代码如下：

1
2
3
4
5
6
7
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];
}
---------------------本文结束---------------------