笔记整理数据结构 c 算法串

DataStructure3（串）

zhangzhang2025-11-022025-11-05

串

4.1串的定义和实现

4.1.1串的定义

串: 零个或多个字符组成的有限序列，如 S = ‘iPhone 11 Pro Max?’；
串名：S是串名；
串的长度：串中字符的个数n；
空串：n=0时的串；
子串：串中任意多个连续的字符组成的子序列称为该串的子串；
主串：包含子串的串；
字符在主串中的位置：某个字符在串中的序号（从1开始）；
子串在主串中的位置：子串的第一个字符在主串中的位置；
空串 V.S 空格串：
- M = ‘’ 是空串；
- N = ’ ’ 是空格串；
串 V.S 线性表：
- 串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）；
- 串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符…
- 串的基本操作，如增删改除通常以子串为操作对象

4.1.2串的基本操作

假设有串 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联接而成的新串———可能会导致存储空间的扩展；

1
2
3

Concat(&T, S, W)

T = ‘iPhone 11 Pro Max?Pro’

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

1
2
3

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.3串的存储结构

1定长顺序存储表示

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

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

串长的两种表示法：
方案一：用一个额外的变量length来存放串的长度（保留ch[0]）；
方案二：用ch[0]充当length；

优点：字符的位序和数组下标相同；

方案三：没有length变量，以字符’\0’表示结尾（对应ASCII码的0）；

缺点：需要从头到尾遍历；

**方案四——最终使用方案：**ch[0]废弃不用，声明int型变量length来存放串的长度（方案一与方案二的结合）
基本操作实现（基于方案四）

#define MAXLEN 255

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

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

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

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

2.堆分配存储表示

**堆存储结构的特点：**仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的。
通常，C语言提供的串类型就是以这种存储方式实现的。由动态分配函数malloc()分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址。由free()释放串不再需要的空间，

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

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

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

3.串的链式存储

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

问题：存储密度低，每个字符1B，每个指针4B；

解决方案：每一个链表的结点存储多个字符——每个结点称为块——块链结构

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

结合链表思考优缺点

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

4.2串的模式匹配

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

4.2.1朴素模式匹配算法（暴力匹配）

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

i = i - j + 2 是 朴素模式匹配算法（暴力匹配） 中，当主串与模式串匹配失败时，主串指针 i 的回溯公式，作用是将主串指针调整到 “下一个可能的匹配起点”。

具体逻辑拆解：
1. 背景：
  
  假设匹配过程中，主串 S 的第 i 个字符与模式串 T 的第 j 个字符不匹配（即 S.ch[i] != T.ch[j]）。
2. 公式含义：
  - i - j + 1：计算本次匹配的起始位置（主串中本次开始匹配的第一个字符的下标）。
  - +1：将起始位置后移一位，作为下一次匹配的新起点。
  合并后即 i = (i - j + 1) + 1 = i - j + 2，表示主串指针从 “本次匹配的下一个位置” 重新开始匹配。
示例说明：
假设主串 S = "abcabcabd"，模式串 T = "abcabd"：
- 首次匹配时，i=1, j=1 开始，前 5 个字符均匹配（S[1-5] = "abcab"，T[1-5] = "abcab"），此时 i=6, j=6。
- 第 6 个字符不匹配（S[6] = 'c' vs T[6] = 'd'），触发 i = 6 - 6 + 2 = 2，j=1。
- 主串指针 i 回溯到 2，从 S[2] 开始重新匹配，以此类推。

时间复杂度分析：

主串长度为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)

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

求 KMP 的next数组其实核心就一个逻辑：找模式串中当前位置前的 “最长相等前后缀” 长度，再做简单调整，咱们用 “例子 + 步骤 + 通俗解释” 一步步拆，保证懂！

先明确 2 个关键概念（必须先会）

前缀：从字符串开头到某个位置，不包含最后一个字符的子串（比如 “abaab” 的前缀有 “a”“ab”“aba”“abaa”）。
后缀：从某个位置到字符串结尾，不包含第一个字符的子串（比如 “abaab” 的后缀有 “b”“ab”“aab”“baab”）。
最长相等前后缀长度：前缀和后缀中完全相同的子串里，最长的那个的长度（比如 “abaab” 的最长相等前后缀是 “ab”，长度 2）。

`next[j]`的本质公式（记死）

next[j] 对应模式串第j个字符（下标从 1 开始，和你给的代码一致），规则：

next[1] = 0（固定！第一个字符失配，模式串右移 1 位）；
next[2] = 1（固定！第二个字符失配，只能回头匹配第一个字符）；
对于j≥3：next[j] = 最长相等前后缀长度 + 1（如果没有相等前后缀，长度为 0，所以next[j]=1）。

实战例子：求模式串`T="abaabc"`（下标 1-6）的`next`数组

模式串索引（j）：1 2 3 4 5 6

模式串字符（T [j]）：a b a a b c

咱们逐个求next[1]到next[6]：

1. 求`next[1]`

j=1，对应字符 “a”；
规则 1：next[1] = 0（固定）。

2. 求`next[2]`

j=2，对应字符 “b”；
规则 2：next[2] = 1（固定）。

3. 求`next[3]`（j=3，字符 “a”）

步骤 1：找 “j=3 之前的子串”—— 即T[1..2] = "ab"；
步骤 2：找 “ab” 的最长相等前后缀：
- 前缀：“a”；后缀：“b”；没有相等的，长度 = 0；
步骤 3：next[3] = 0 + 1 = 1。

4. 求`next[4]`（j=4，字符 “a”）

步骤 1：j=4 之前的子串是T[1..3] = "aba"；
步骤 2：找 “aba” 的最长相等前后缀：
- 前缀：“a”“ab”；后缀：“a”“ba”；
- 最长相等的是 “a”，长度 = 1；
步骤 3：next[4] = 1 + 1 = 2。

5. 求`next[5]`（j=5，字符 “b”）

步骤 1：j=5 之前的子串是T[1..4] = "abaa"；
步骤 2：找 “abaa” 的最长相等前后缀：
- 前缀：“a”“ab”“aba”；后缀：“a”“aa”“baa”；
- 最长相等的是 “a”，长度 = 1；
步骤 3：next[5] = 1 + 1 = 2。

6. 求`next[6]`（j=6，字符 “c”）

步骤 1：j=6 之前的子串是T[1..5] = "abaab"；
步骤 2：找 “abaab” 的最长相等前后缀：
- 前缀：“a”“ab”“aba”“abaa”；后缀：“b”“ab”“aab”“baab”；
- 最长相等的是 “ab”，长度 = 2；
步骤 3：next[6] = 2 + 1 = 3。

最终`next`数组结果

j：1 2 3 4 5 6

next[j]：0 1 1 2 2 3

更高效的推导技巧（避免重复比较）

如果 j 较大，不想每次都重新找前后缀，可以用 “回溯法”（基于前一个next值）：

比如求next[j]时，先看next[j-1]的值（假设是 k）（next[j-1] = k）：

比较T[j-1]和T[k]：如果相等，next[j] = k + 1；
如果不相等，就把 k 换成next[k]（回溯到更短的前后缀），再比较，直到 k=0（此时next[j]=1）。

再验证一个简单例子：模式串`T="ababaaababaa"`（之前的题）

j：1 2 3 4 5 6 7 8 9 10 11 12

T[j]：a b a b a a a b a b a a

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

比如 j=5（字符 “a”），前子串 “abab”，最长相等前后缀 “ab”（长度 2），next[5]=3；
j=6（字符 “a”），前子串 “ababa”，最长相等前后缀 “aba”（长度 3），next[6]=4；
完全符合之前的逻辑！

总结：求`next`数组 3 步走

给模式串标上 1 开始的下标 j；
j=1→0，j=2→1（固定）；
j≥3：
- 取 j 前面的子串（T [1] 到 T [j-1]）；
- 找这个子串的 “最长相等前后缀长度”；
- 长度 + 1 就是next[j]（长度为 0 则next[j]=1）。

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

1.求next数组

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

2.利用`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; //匹配成功
}

3.时间复杂度分析

求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