4.1 串的定义

串的基本操作

• StrAssign(s, str)：将 str 赋给 s
• StrLength(s)：求串长
• StrCompare(s, t)：比较两个串的大小
• Concat(s, t)：串连接
• SubString(s, pos, len)：求子串
• Index(s, t)：子串定位（模式匹配）
• Replace(s, t, v)：子串替换

4.2 串的存储结构

1. 顺序存储

用数组存储串值。有两种方式：

• 静态数组：预先分配固定长度，空间利用率低
• 动态数组：按实际长度分配，如 C++ 的 string

2. 链式存储

每个结点存储一个或多个字符。结点大小为 1 时操作方便但指针开销大；结点大小大于 1 时可压缩存储，但操作更复杂。

4.3 串的模式匹配（BF 算法）

BF 算法（朴素匹配 / Brute Force）

从主串 s 的第一个字符开始，与模式串 t 逐字符比较；若匹配失败，从 s 的下一个字符重新开始比较。时间复杂度 O(n·m)。

int BF(String s, String t){
  int i=0, j=0;
  while(i<s.length && j<t.length){
    if(s[i]==t[j]){ i++; j++; }
    else{ i=i-j+1; j=0; }   // 回退
  }
  if(j==t.length) return i-j;   // 匹配成功
  return -1;                        // 匹配失败
}

4.4 KMP 算法

KMP 算法通过预处理模式串，构建 next 数组（也叫失配函数），在匹配失败时利用已匹配信息跳过不必要的比较，避免了主串指针的回退。时间复杂度 O(n+m)。

1. next 数组的含义

next[j] 表示：当模式串 t 中第 j 个字符与主串中相应字符不匹配时，在模式串中需要重新与主串中该字符进行比较的位置。即 t[j] 前的子串 t[0..j-1] 的最长公共前后缀长度。

2. next 数组的计算

next[0] = -1;   // 特殊标记
for(j=1; j<m; j++){
  i = next[j-1];
  while(i>=0 && t[i]!=t[j-1]) i = next[i];
  next[j] = i + 1;
}

3. KMP 匹配过程

int KMP(String s, String t){
  int i=0, j=0;
  while(i<s.length && j<t.length){
    if(j==-1 || s[i]==t[j]){ i++; j++; }
    else{ j = next[j]; }   // 利用 next 跳过
  }
  if(j==t.length) return i-j;
  return -1;
}

4.5 各模式匹配算法对比