数据结构与算法 第四章 串

4.1 串的定义和基本操作

串：即字符串，由 零个或多个 字符组成的有限序列，记为S=‘a₁a₂…a_n’（n>=0），n等于0时为空串

子串：串中任意个连续的字符组成的子序列

主串：包含子串的串

字符在主串中的位置：字符在串中的序号

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

串是特殊的线性表，元素之间呈线性关系，数据对象限定为字符集，基本操作（如增删改查）以子串为操作对象

串的基本操作

StrAssign(&T,chars)：把串T赋值为chars

StrCopy(&T,S)：由串S复制得到串T

StrEmpty(S)：若S为空串返回true,否则返回false

StrLength(S)：返回串S的元素个数

ClearString(&S)：将S清为空串

DestroyString(&S)：将串S销毁（回收存储空间）

Concat(&T,S1,S2)：用T返回由S1和S2联接而成的新串

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

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

StrCompare(S,T)：若S>T,则返回值>0；若S=T,则返回值=0；若S<T,则返回值<0

串的比较操作

4.2 串的存储结构

串的顺序存储

// 静态数组实现
#define MAXLEN 255	// 预定义最大串长为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

串顺序存储的方案有四种。

第一种字符从下标0开始存储，另外用length变量存储串的大小。

第二种下标0的存储空间用来存储length变量，使得字符从下标1开始存储，字符的位序与数组下标相同，缺点是char[0]只能表示0到255，串长度一旦超过255，变无法继续计数。

第三种没有length变量，以\0作为结束字符，但是需要知道该串的长度时就需要从头到尾遍历一遍计数，麻烦。

第四种，char[0]舍弃不用，额外用length变量记录串大小，结合了第一、二中方案的优点。

串的链式存储

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

// 由于每个字符占1B，每个指针占4B，导致存储密度很低，所以可以将几个字符连续存储
typedef struct StringNode{
    char ch[4];	// 每个结点存1个字符
    struct StringNode *next;
}StringNode,*String;

基本操作的实现

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.length=len;
    return true;
}

StrCompare(S,T)：若S>T,则返回值>0；若S=T,则返回值=0；若S<T,则返回值<0

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

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相等的子串
}

4.3 朴素模式匹配算法

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

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所以的子串都不匹配为止，最多对比n-m+1个子串

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 i-T.length;
    else:
    	return 0;
}

最坏的情况，每个子串需要对比m个字符，共n-m+1个子串，复杂度=O((n-m+1)m)，由于n>>m，所以时间复杂度约等于O(nm)

4.4 KMP算法

next数组表示当模式串t[j]的字符与主串s[i]的字符不匹配时，j应该跳到next[j]的字符继续匹配

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;
}

最坏时间复杂度是O(m+n)，其中求next数组时间复杂度O(m)，模式匹配过程最坏时间复杂度O(n)

4.5 求next数组

next[0]都无脑写0

next[1]都无脑写1

其他next[j]：在不匹配的为止前，划一根分界线，模式串一步一步往后退，直到分界线之前能对上，或模式串完全跨过分界线为止。此时j指向哪，next[j]数组值就是多少

4.6 KMP算法的进一步优化

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];
}