4 串

[4] 串

基本概念

T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'

名词	解释
串	零个或多个字符组成的有限序列，如 `S = 'iPhone 11 Pro Max?'`
串名	S 是串名
串的长度	串中字符的个数 n
空串	n=0 时的串
子串	串中任意多个连续的字符组成的子序列称为该串的子串
主串	包含子串的串
字符在主串中的位置	某个字符在串中的序号（从 1 开始）
子串在主串中的位置	子串的第一个字符在主串中的位置

M = ‘’ 是空串； N = ’ ’ 是空格串；
串和线性表：串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）；串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符… 串的基本操作，如增删改除通常以子串为操作对象

基本操作

T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'

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 联接而成的新串———可能会导致存储空间的扩展；
c
```
Concat(&T, S, W)
T = 'iPhone 11 Pro Max?Pro'
```
SubString(&Sub, S, pos, len): 求子串，用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串；
c
```
SubString(&T, S, 4, 6)
T = 'one 11'
```
Index(S, T): 定位操作，若主串 S 中存在与串 T 值相同的子串，则返回它再主串 S 中第一次出现的位置，否则函数值为 0；
StrCompare(S, T): 串的比较操作，参照英文词典排序方式；若 S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;

存储结构

[4-1] 顺序串

4 种储存方案

通过数组声明存放

#define MAXLEN 255   //预定义最大串长为255

typedef struct{
    char ch[MAXLEN];   //静态数组实现（定长顺序存储）
                       //每个分量存储一个字符
                       //每个char字符占1B
    int length;        //串的实际长度
}SString;

串长的两种表示法（串数据结构的常用设计方法）：

方案一：用一个额外的变量 length 来存放串的长度（保留ch[0]）；
方案二：用ch[0]充当 length；(短串，长度最大为 255？个人认为比较简洁) 优点：字符的位序和数组下标相同；
方案三：没有 length 变量，以字符'\0'表示结尾（对应 ASCII 码的 0）；缺点：需要从头到尾遍历；
方案四（推荐方案）：ch[0]废弃不用，声明 int 型变量 length 来存放串的长度（方案一与方案二的结合）

基本操作实现（基于方案四）

{0}

#define MAXLEN 255

typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

{6-x} 求子串

// 1. 求子串
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.cn[i-pos+1] = S.ch[i];

    Sub.length = len;

    return true;
}

{6-x} 比较两个串的大小

// 2. 比较两个串的大小
int StrCompare(SString S, SString T){
    for (int i; 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;
}

{6-x} 定位操作

// 3. 定位操作
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相等的子串
}

堆区连续存放

堆存储结构的特点：仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的

通常，C 语言提供的串类型就是以这种存储方式实现的。由动态分配函数 malloc()分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址。由 free()释放串不再需要的空间

堆存储结构的优点**：**堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。

//动态数组实现
typedef struct{
    char *ch;           //按串长分配存储区，ch指向串的基地址
    int length;         //串的长度
}HString;

HString S；
S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指针指向连续空间的起始位置
                                                //malloc()需要手动free()
S.length;

[4-2] 链串

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

问题：存储密度低，每个字符 1B，每个指针 4B；解决方案：每一个链表的结点存储多个字符，每个结点称为块 → 块链结构

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

结合链表思考优缺点

存储分配角度：链式存储的字符串无需占用连续空间，存储空间分配更灵活；
操作角度：若要在字符串中插入或删除某些字符，则顺序存储方式需要移动大量字符，而链式存储不用；
若要按位序查找字符，则顺序存储支持随机访问，而链式存储只支持顺序访问；

[KMP 算法] 串的模式匹配

模式匹配：子串的定位操作称为串的模式，它求的是子串（常称模式串）在主串中的位置。

朴素模式匹配算法

思想：遍历匹配字串第一个，如果某次匹配上了则继续下一个……，匹配失败访问本次匹配头的下一个位置

int Index(SString S, SString T){
    int i=1;                // 扫描主串S
    int j=1;                // 扫描模式串T
    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;
}

时间复杂度分析：

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

最坏时间复杂度 = O(nm) 每个子串都要对比 m 个字符(对比到最后一个字符才匹配不上)，共要对比 n-m+1 个子串，复杂度 = O((n-m+1)m) = O(nm - m^2 + m) = O(nm) PS:大多数时候，n>>m

最好时间复杂度 = O(n) 每个子串的第一个字符就匹配失败，共要对比 n-m+1 个子串，复杂度 = O(n-m+1) = O(n)

改进的模式匹配算法——KMP 算法

不匹配的字符之前，一定是和模式串一致的；根据模式串 T，求出 next 数组（只与模式串有关，与主串无关），利用 next 数组进行匹配，当匹配失败时，主串的指针 i 不再回溯！ next 数组是根据子串求出来的，当前面的字符串已知时如果有重复的，从当前的字符匹配即可。

求 next 数组作用：当模式串的第 j 个字符失配时，从模式串的第 next[j]继续往后匹配; 对于任何模式串，当第 1 个字符不匹配时，只能匹配下一个子串，因此，next[1] = 0——表示模式串应右移一位，主串当前指针后移一位，再和模式串的第一字符进行比较；对于任何模式串，当第 2 个字符不匹配时，应尝试匹配模式串的第一个字符，因此，next[2] = 0; 例：对于串 T = 'abaabc'

next[0]是不放东西，无作用的

利用 next 数组进行模式匹配

int Index_KMP(SString S, SString T, int next[]){
    int i=1;     //主串
    int j=1;     //模式串
    while（i<S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){      //第一个元素匹配失败时
            ++j;
            ++i;         //继续比较后继字符
        }
        else
            j=next[j]   //模式串向右移动
    }
    if(j>T.length)
        return i-T.length; //匹配成功
}

时间复杂度分析

求 next 数组时间复杂度 = O(m)
模式匹配过程最坏时间复杂度 = O(n)
KMP 算法的最坏时间复杂度 = O(m+n)

next 数组的求法：

我们能确定 next 数组第一二位一定分别为 0，1，后面求解每一位的 next 值时，根据前一位进行比较。从第三位开始，将前一位与其 next 值对应的内容进行比较，如果相等，则该位的 next 值就是前一位的 next 值加上 1；如果不等，向前继续寻找 next 值对应的内容来与前一位进行比较，直到找到某个位上内容的 next 值对应的内容与前一位相等为止，则这个位对应的值加上 1 即为需求的 next 值；如果找到第一位都没有找到与前一位相等的内容，那么求解的位上的 next 值为 1。

注意下标都是从 1 开始的传送门：https://blog.csdn.net/m0_37482190/article/details/86667059

钤元解释怎么求 next

当 i 不匹配时，相同的字符串需要出现在1~x和(i-x)~(i-1)之间，我要证明，为什么通过那种求法得到的数组可以使用
假设我们的数组为 ab*********ab，*中没有匹配 ab 的字符串，第二个 a 最先出现时，next 值为 1，计算第二个 b 时，我们看向第二个 a，发现下标 1 也是 a,于是第二个 b 下标为 1+1

4 串 ​

[4] 串 ​

基本概念 ​

基本操作 ​

存储结构 ​

[4-1] 顺序串 ​

4 种储存方案 ​

{0} ​

{6-x} 求子串 ​

{6-x} 比较两个串的大小 ​

{6-x} 定位操作 ​

堆区连续存放 ​

[4-2] 链串 ​

[KMP 算法] 串的模式匹配 ​

朴素模式匹配算法 ​

改进的模式匹配算法——KMP 算法 ​

钤元解释怎么求 next ​

4 串