DSA - 串 + 习题集

发表于 2026-06-19 分类于数据结构阅读次数：本文字数： 1.7k 阅读时长 ≈ 6 分钟

DSA 的字符串算法。最近看了好多漫画。

KMP 算法

i 将永远不必回退。比对成功就一起进一格，否则 j 更新为某个更小的值并继续在原位比较。

为此需要构造 next 表，使得一旦在 P [j] 处失配就将 j 替换为 next [j] 继续与 T [i] 比对。

0001 int match( char* T, char* P ) {  //KMP算法
0002    int* next = buildNext( P ); //构造next表
0003    int n = ( int ) strlen( T ), i = 0; //文本串指针
0004    int m = ( int ) strlen( P ), j = 0; //模式串指针
0005    while ( (j < m) && (i-j <= n-m) ) //自左向右逐个比对字符
0006       if ( 0 > j || T[i] == P[j] ) //若匹配，或P已移出最左侧（两个判断的次序不可交换）
0007          { i ++;  j ++; } //则转到下一字符
0008       else //否则
0009          j = next[j]; //模式串右移（注意：文本串不用回退）
0010    delete [] next; //释放next表
0011    return i - j;
0012 }

抽象出来的匹配算法。

因为 i 从来不后退，所以 i 的位置就是当前已经成功匹配的次数，于是 O (n)；朴素 KMP 的话如果匹配串是重复的同一个字母，每个元素的 next 都是前一个元素，那么 T [i] 需要匹配 m 次。

对匹配串构造一个类似这样的 next 表。要求是 next 所指位置的前缀，和当前位置的前缀能匹配。在匹配串前面补哨兵。第一个元素一定指向哨兵

$N (P,j)={0<=t < j|P [0,t)=P [j-t,j)}$，所有自匹配的长度取最大值 maxN (p,j) 为最大长度。

$j->next [j]->next^2 [j]->…->0->-1$，next 构成传递链

为求 P [j + 1] 的 next 数组，如果 P [j]==P [next [j]] 说明 j 的前缀和 next [j] 的前缀相等，算上 j 和 next [j] 本身就是 j + 1 和 next [j]+1 的前缀相等, 那么 next [j + 1]=next [j]+1；如果不相等就找下家，也就是其他能让 j 的前缀与之匹配的位置，也就是 next 链的下一个，这是 j + 1 能与之匹配的必要条件。

0001 int* buildNext( char* P ) { //构造模式串P的next表
0002    int m = strlen( P ), j = 0; //“主”串指针
0003    int* next = new int[m]; int t = next[0] = -1; //next表，首项必为-1
0004    while ( j < m - 1 )
0005       if ( 0 > t || P[t] == P[j] ) { //匹配
0006          ++t; ++j; next[j] = t; //则递增赋值：此处可改进...
0007       } else //否则
0008          t = next[t]; //继续尝试下一值得尝试的位置
0009    return next;
0010 }

摊还分析

令 k = 2*i-j

k<=2n-1, 所以是线性的。

k = i+(i-j)= 主串移动 + 相对移动偏移量（也就是匹配串相对于主串的位置），匹配上了主串和匹配串一起移动 1 格，没匹配上匹配串向前移动至少 1 格。想想两个滑块的移动。

因为 i 只会向前动；因为失败一次对齐位置就移动了，也就是匹配串向前滑动，而且不会回头。什么叫通配符出现失败比对啊没看懂。

改进

如果出现跳到 next 的位置不改变当前匹配字符，那一定会发生失配，这种情况可以优化掉。

代码容易看懂不过多赘述。

0001 int* buildNext( char* P ) { //构造模式串P的next表（改进版本）
0002    int m = strlen( P ), j = 0; //“主”串指针
0003    int* next = new int[m]; int t = next[0] = -1; //next表，首项必为-1
0004    while ( j < m - 1 )
0005       if ( 0 <= t && P[t] != P[j] ) //失配
0006          t = next[t]; //继续尝试下一值得尝试的位置
0007       else //匹配
0008          if ( P[++t] != P[++j] ) //附加条件判断
0009             next[j] = t; //唯当新的一对字符也匹配时，方照原方法赋值
0010          else
0011             next[j] = next[t]; //否则，改用next[t]（此时必有：P[next[t]] != P[t] == P[j]）
0012    return next;
0013 }

不可能。在考虑 next [j] 处时已经避免了相等的出现，一旦出现就覆盖掉了。

不会。

BM 算法

BC 策略：

构造 bc 表，匹配串从后往前匹配直到第一个失配的 X - Y，此时在匹配串里找 X 出现的最靠右的位置 bc [‘X’]，匹配串右移 j-bc [‘X’]。为了避免陷入死循环，shift 必须至少 = 1。这样匹配串就只会向前不会后退。

0001 int match( char* T, char* P ) { //Boyer-Morre算法（简化版，只考虑Bad Character Shift）
0002    int* bc = buildBC( P ); //预处理
0003    int n = strlen( T ), i = 0;
0004    int m = strlen( P ), j = m-1;
0005    while ( (0 <= j) && (i <= n-m) ) //自右向左逐个比对字符
0006       if (T[i + j] == P[j]) //若匹配
0007          j--; //则转到下一对字符
0008       else //否则
0009          { i += max(1, j - bc[T[i+j]]); j = m-1; } //借助BC表快速右移模式串
0010    delete [] bc; return i; //销毁BC表，返回最终的对齐位置
0011 }