串

4.1 串的定义

串（String）是由零个或多个字符组成的有限序列。记为 S = 'a₁a₂...aₙ'，其中 aᵢ 是字符，n 是串的长度。

  • 空串：长度为 0 的串，记为 ''。
  • 空格串：由空格字符组成的串，如 ' '。
  • 子串：串中任意连续字符组成的子序列。
  • 主串：包含子串的串。
  • 子串位置：子串第一个字符在主串中的位置（通常从 1 开始计数）。

举例：S = 'Hello World'，则 'World' 是 S 的子串，位置为 7（从 1 开始计）。

串与线性表的区别：串的操作对象是字符，通常以"子串"为基本操作单位。

基本操作：

  • StrAssign(&T, chars)：赋值操作
  • StrCopy(&T, S)：串复制
  • StrCompare(S, T)：串比较，返回值 <0、=0、>0
  • StrLength(S)：求串长
  • Concat(&T, S1, S2)：串连接
  • SubString(&Sub, S, pos, len)：求子串
  • Index(S, T)：子串定位，若 T 是 S 的子串则返回位置

💡 记忆技巧：串的操作和线性表类似，但"查找"变成了"子串定位"（模式匹配），这是串的核心操作。

4.2 串的存储结构

定长顺序存储

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

使用固定长度的字符数组，超出 MAXLEN 的部分会被截断。

堆分配存储

typedef struct {
    char *ch;
    int length;
} HString;

使用 malloc 和 free 动态管理内存，灵活但需要手动管理。

块链存储

每个结点存放若干个字符，结点之间用指针链接。块链存储的空间利用率比顺序存储低，但插入和删除方便。

三种存储方式比较：

存储方式 优点 缺点
定长顺序存储 实现简单，随机存取 长度固定，可能截断
堆分配存储 灵活，长度可变 需手动管理内存
块链存储 插入删除方便 存储密度低，实现复杂

4.3 串的基本操作实现

求子串：从主串 S 的第 pos 个位置开始取长度为 len 的子串。需检查 pos 和 len 的合法性（pos ≥ 1, len ≥ 0, pos+len-1 ≤ S.length），然后将 S.ch[pos..pos+len-1] 复制到子串 T。

串比较：从第一个字符开始逐对比较字符编码值（如 ASCII），直到出现不同或到达串尾。若所有字符相同，则长度更长的串更大。C 语言的 strcmp 就是这种原理。

子串定位（Index 操作）：这是串最核心的操作，即模式匹配——在长串（主串）中寻找短串（模式串）第一次出现的位置。

4.4 朴素模式匹配算法（BF算法）

BF（Brute-Force）算法是最直观的模式匹配方法。

算法思路：从主串 S 的第一个字符开始，与模式串 T 的第一个字符比较。若匹配，则继续比较后续字符；若不匹配，则从主串的下一个字符重新开始比较。

int BF(char S[], char T[]) {
    int i = 1, j = 1;
    while (i <= S[0] && j <= T[0]) {  // S[0]和T[0]存储串长
        if (S[i] == T[j]) { i++; j++; }
        else { i = i - j + 2; j = 1; }
    }
    if (j > T[0]) return i - T[0];
    else return 0;
}

时间复杂度：

  • 最好情况：O(m)，第一次比较就匹配成功。
  • 最坏情况：O(nm)，如 S = 'AAAAAAAAAB'，T = 'AAAAB'，每次匹配到最后一个字符才失败（n 为主串长度，m 为模式串长度）。
  • 平均情况：O(n + m)（在随机文本下效率尚可）。

⚠️ 易错点：BF算法匹配失败时 i 的回退位置是 i = i - j + 2（从 1 开始计数），不要搞错。

4.4 KMP算法（重点）

KMP 算法由 Knuth、Morris 和 Pratt 三位科学家提出，利用已匹配部分的信息避免 i 的回退，将时间复杂度降到 O(n + m)。

核心思想：当某次匹配失败时，主串指针 i 不回溯，模式串指针 j 根据 next 数组回退到合适的位置继续匹配。

next数组的求法

next[j] 表示当模式串中第 j 个字符匹配失败时，j 应该回退到的位置。

定义：next[j] = k，其中 k 满足：

  • P₁...Pₖ₋₁ = Pⱼ₋ₖ₊₁...Pⱼ₋₁（即长度为 k-1 的最长相等前后缀）
  • 若没有相等的前后缀，则 next[j] = 1

手算方法：

  1. next[1] = 0（特殊标记，表示 i 也应该后移）。
  2. next[2] = 1（第二个字符的前缀只有第一个字符，但前缀不能等于整个子串，所以固定为 1）。
  3. 对于 j ≥ 3，看 P₁...Pⱼ₋₁ 的最长相等前后缀长度 len，则 next[j] = len + 1。

举例：模式串 'ABABAA' 的 next 数组计算

j:    1  2  3  4  5  6
P:    A  B  A  B  A  A
next: 0  1  1  2  3  4

计算过程：

  • j=1：next[1] = 0
  • j=2：next[2] = 1
  • j=3：P₁P₂ = 'AB'，没有相等前后缀，next[3] = 1
  • j=4：P₁P₂P₃ = 'ABA'，最长相等前后缀为 'A'（长度1），next[4] = 1+1 = 2
  • j=5：P₁P₂P₃P₄ = 'ABAB'，最长相等前后缀为 'AB'（长度2），next[5] = 2+1 = 3
  • j=6：P₁P₂P₃P₄P₅ = 'ABABA'，最长相等前后缀为 'ABA'（长度3），next[6] = 3+1 = 4

nextval数组（优化）

nextval 是对 next 数组的进一步优化，避免不必要的匹配。 规则：若 P[j] == P[next[j]]，则 nextval[j] = nextval[next[j]]；否则 nextval[j] = next[j]。

举例：接上例

j:      1  2  3  4  5  6
P:      A  B  A  B  A  A
next:   0  1  1  2  3  4
nextval:0  1  0  1  0  4

计算过程：

  • j=1：nextval[1] = 0
  • j=2：P[2]=B，P[next[2]]=P[1]=A，不同，nextval[2]=next[2]=1
  • j=3：P[3]=A，P[next[3]]=P[1]=A，相同，nextval[3]=nextval[1]=0
  • j=4：P[4]=B，P[next[4]]=P[2]=B，相同，nextval[4]=nextval[2]=1
  • j=5：P[5]=A，P[next[5]]=P[3]=A，相同，nextval[5]=nextval[3]=0
  • j=6：P[6]=A，P[next[6]]=P[4]=B，不同，nextval[6]=next[6]=4

KMP匹配过程

int KMP(char S[], char T[], int next[]) {
    int i = 1, j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) { i++; j++; }
        else j = next[j];
    }
    if (j > T[0]) return i - T[0];
    else return 0;
}

KMP匹配全过程示例：

主串 S: ABABABABABCA
模式串 T: ABABAA
next:  0 1 1 2 3 4

i=1,j=1: A=A → i=2,j=2
i=2,j=2: B=B → i=3,j=3
i=3,j=3: A=A → i=4,j=4
i=4,j=4: B=B → i=5,j=5
i=5,j=5: A=A → i=6,j=6
i=6,j=6: B≠A → j=next[6]=4
i=6,j=4: B=B → i=7,j=5
i=7,j=5: A=A → i=8,j=6
i=8,j=6: B≠A → j=next[6]=4
i=8,j=4: B=B → i=9,j=5
i=9,j=5: A=A → i=10,j=6
i=10,j=6: C≠A → j=next[6]=4
i=10,j=4: C≠B → j=next[4]=2
i=10,j=2: C≠B → j=next[2]=1
i=10,j=1: C≠A → j=next[1]=0
i=11,j=1: A=A → i=12,j=2
i=12,j=2: A≠B → j=next[2]=1
i=12,j=1: A=A → i=13,j=2
i=13 > S[0]=12, 退出
匹配失败，返回0

📌 408考点提示：KMP 算法是串这一章的核心考点，几乎每年都会涉及：

  • 手动计算 next 和 nextval 数组（选择题或填空题）
  • KMP 匹配过程中指针的变化轨迹
  • 注意 next 数组的起始计数可能不同（0-based 或 1-based），题目中明确即可

4.5 题型示例

例题1：已知模式串 'abaabcac'，求 next 数组和 nextval 数组。

解：

j:    1  2  3  4  5  6  7  8
P:    a  b  a  a  b  c  a  c
next: 0  1  1  2  2  3  1  2
nextval:0 1  0  2  1  3  0  2

next 计算：

  • j=1: next[1]=0
  • j=2: next[2]=1
  • j=3: 'a'与'b'不同，next[3]=1
  • j=4: 'a'与'a'相同，长度1，next[4]=2
  • j=5: 子串'abaa'，前缀'a'='a'后缀，长度1，next[5]=2
  • j=6: 子串'abaab'，前缀'ab'='ab'后缀，长度2，next[6]=3
  • j=7: 子串'abaabc'，没有相等前后缀，next[7]=1
  • j=8: 子串'abaabca'，前缀'a'='a'后缀，长度1，next[8]=2

nextval 计算：

  • j=1: nextval[1]=0
  • j=2: P[2]=b, P[next[2]]=P[1]=a, 不同，nextval[2]=next[2]=1
  • j=3: P[3]=a, P[next[3]]=P[1]=a, 相同，nextval[3]=nextval[1]=0
  • j=4: P[4]=a, P[next[4]]=P[2]=b, 不同，nextval[4]=next[4]=2
  • j=5: P[5]=b, P[next[5]]=P[2]=b, 相同，nextval[5]=nextval[2]=1
  • j=6: P[6]=c, P[next[6]]=P[3]=a, 不同，nextval[6]=next[6]=3
  • j=7: P[7]=a, P[next[7]]=P[1]=a, 相同，nextval[7]=nextval[1]=0
  • j=8: P[8]=c, P[next[8]]=P[2]=b, 不同，nextval[8]=next[8]=2

例题2：主串 S='ababcabcacbab'，模式串 T='abcac'，写出 KMP 匹配过程。

解： 先求 T 的 next 数组：

j:    1  2  3  4  5
P:    a  b  c  a  c
next: 0  1  1  1  2

匹配过程：

i=1,j=1: a=a → i=2,j=2
i=2,j=2: b=b → i=3,j=3
i=3,j=3: a≠c → j=next[3]=1
i=3,j=1: a=a → i=4,j=2
i=4,j=2: b=b → i=5,j=3
i=5,j=3: c=c → i=6,j=4
i=6,j=4: a=a → i=7,j=5
i=7,j=5: b≠c → j=next[5]=2
i=7,j=2: b=b → i=8,j=3
i=8,j=3: c=c → i=9,j=4
i=9,j=4: a=a → i=10,j=5
i=10,j=5: c=c → i=11,j=6
j>5, 匹配成功！位置 = i - T[0] = 11 - 5 = 6

例题3：对比 BF 算法和 KMP 算法，分析在 S='AAAAAAAAAAB'、T='AAAAB' 时的匹配次数。

解：

  • BF：每次匹配到最后一个字符 B 时发现不匹配，i 回退到下一个位置。S 长度 11，每次从匹配起始到下一位，共调用约 7 次匹配，每次匹配 5 次，共约 35 次字符比较。
  • KMP：next[1]=0, next[2]=1, next[3]=2, next[4]=3, next[5]=4。匹配失败时 j 只回退一位，i 从不回溯。共需约 11+5 = 16 次字符比较。KMP 效率明显更高。

例题4：已知主串 S='BBC ABCDAB ABCDABCDABDE'，模式串 T='ABCDABD'，求 next 数组并写出 KMP 匹配过程。

解： 先求 T 的 next 数组：

j:    1  2  3  4  5  6  7
P:    A  B  C  D  A  B  D
next: 0  1  1  1  1  2  3

计算说明：

  • j=1: 0
  • j=2: 1
  • j=3: 'AB'无相等前后缀 → 1
  • j=4: 'ABC'无 → 1
  • j=5: 'ABCD'无 → 1
  • j=6: 子串'ABCDA'，前缀'A'='A'后缀 → next[6]=2
  • j=7: 子串'ABCDAB'，前缀'AB'='AB'后缀 → next[7]=3

KMP 匹配过程（主串 S 中依次匹配，i 不回溯）：

i=1,j=1: B≠A → j=0 → i=2,j=1
i=2,j=1: B≠A → j=0 → i=3,j=1
i=3,j=1: C≠A → j=0 → i=4,j=1
i=4,j=1: 空格≠A → j=0 → i=5,j=1
i=5,j=1: A=A → i=6,j=2
i=6,j=2: B=B → i=7,j=3
i=7,j=3: C=C → i=8,j=4
i=8,j=4: D=D → i=9,j=5
i=9,j=5: A=A → i=10,j=6
i=10,j=6: B=B → i=11,j=7
i=11,j=7: 空格≠D → j=next[7]=3
i=11,j=3: 空格≠C → j=next[3]=1
i=11,j=1: 空格≠A → j=0 → i=12,j=1
i=12,j=1: A=A → i=13,j=2
...（继续匹配，最终 i=16,j=7 时匹配成功）

例题5：模式串 'ababaaab'，求 nextval 数组。

解：

j:     1  2  3  4  5  6  7  8
P:     a  b  a  b  a  a  a  b
next:  0  1  1  2  3  4  2  2
nextval:0 1  0  1  0  4  2  1

nextval 计算：

  • j=1: 0
  • j=2: P[2]=b, P[next[2]]=P[1]=a, 不同 → 1
  • j=3: P[3]=a, P[next[3]]=P[1]=a, 相同 → nextval[1]=0
  • j=4: P[4]=b, P[next[4]]=P[2]=b, 相同 → nextval[2]=1
  • j=5: P[5]=a, P[next[5]]=P[3]=a, 相同 → nextval[3]=0
  • j=6: P[6]=a, P[next[6]]=P[4]=b, 不同 → next[6]=4
  • j=7: P[7]=a, P[next[7]]=P[2]=b, 不同 → next[7]=2
  • j=8: P[8]=b, P[next[8]]=P[2]=b, 相同 → nextval[2]=1

本章总结

串的模式匹配是本章的核心。BF 算法简单易懂但效率低，KMP 算法通过 next 数组避免主串回溯，将时间复杂度优化到 O(n+m)。next 数组的手动计算是 408 考试的高频考点，务必熟练掌握。实际解题时，推荐使用 nextval 数组，它比 next 数组更高效。掌握"最长相等前后缀"的概念是理解 KMP 的关键——前后缀不能等于字符串本身。