Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/8.串与模式匹配.md

8. 串与模式匹配

概念

串（String） 是由零个或多个字符组成的有限序列，又称字符串。一般记为 S = "a1 a2 ... an"，其中 n 称为串长，n = 0 时称为空串。串中任意连续字符组成的子序列称为该串的子串。

串在逻辑上是一种特殊的线性表（元素是字符），主要区别在于串的操作对象往往是"子串"而非单个元素。

串的存储结构：

1. 定长顺序存储：用固定长度的字符数组存储串，长度固定，可能截断。
2. 堆分配存储：用动态分配的内存存放串，长度可变化（C 语言中用指针+动态分配，C++ 用 std::string）。
3. 块链存储：用链表存储，每个结点存放若干字符（块），节省指针空间但操作复杂，实际很少使用。

串的基本操作： 串赋值、求串长、串比较、取子串、串定位（模式匹配）等。

模式匹配： 在主串（目标串）S 中查找模式串（子串）T 第一次出现的位置。主要有两种算法：

1. 朴素匹配（BF, Brute Force）：从主串第一个字符开始，与模式串逐个比较；失配时主串指针回溯到下一位置重新比较，简单但效率低。
2. KMP 算法（Knuth-Morris-Pratt）：通过预计算 next 数组，在失配时主串指针不回溯，只移动模式串指针，从而大大提高效率。

KMP 核心思想： 当某次匹配失败时，已经匹配成功的部分存在"部分匹配"信息。通过 next 数组记录模式串中每个位置失配时应跳转到的位置，避免主串回溯、避免重复比较。

核心操作

操作	说明
StrAssign 串赋值	给串赋值
StrLength 求串长	返回串的长度
StrCompare 串比较	按字典序比较两个串
SubString 取子串	返回串中指定位置、长度的子串
Index 串定位	返回子串在主串中的位置
BF/KMP 模式匹配	查找模式串在主串中出现的位置

复杂度分析

算法	时间复杂度	空间复杂度	说明
BF 朴素匹配	最好 O(n)，最坏 O(n×m)	O(1)	最坏情况主串每个位置都要完整比较
KMP 匹配	O(n + m)	O(m)	主串不回溯，整体线性
next 数组构造	O(m)	O(m)	对模式串做一次类 KMP 预处理

为什么：

• BF：主串长度为 n，模式串长度为 m。最坏情况（如主串 "aaaa...ab"、模式串 "aaaab"）下，主串每个起始位置都要比较 m 次，总比较次数约 n×m，故最坏 O(n×m)；最好情况第一个字符就匹配失败，为 O(n)。
• KMP：next 数组构造只需扫描模式串一次，O(m)。匹配过程中主串指针 i 从不回溯、只增不减，最多扫描主串一遍 O(n)，模式串指针虽然会回退，但整体均摊 O(1)，所以匹配总复杂度 O(n)，合计 O(n+m)。
• next 数组需要存储 m 个整数，空间 O(m)。

next 数组的构造

next 数组的含义：当模式串第 j 个字符（下标从 1 起）失配时，模式串应跳到 next[j] 位置继续与主串比较。本质是求模式串前缀子串中最长的"既是前缀又是后缀"的公共部分的长度。

手工计算例子： 模式串 T = "ababaa"（下标从 1 开始）：

• next[1] = 0（约定）。
• next[2]：子串 "ab" 前缀后缀公共部分长度为 0 → next[2] = 1（无公共前后缀则回退到 1）。
• next[3]：子串 "aba"，前缀 "a" = 后缀 "a"，最长公共前后缀长度 1 → next[3] = 1 + 1 = 2。
• next[4]：子串 "abab"，最长公共前后缀 "ab" 长度 2 → next[4] = 2 + 1 = 3。
• next[5]：子串 "ababa"，最长公共前后缀 "aba" 长度 3 → next[5] = 3 + 1 = 4。
• next[6]：子串 "ababaa"，最长公共前后缀 "a" 长度 1 → next[6] = 1 + 1 = 2。

所以 next = [0, 1, 2, 3, 4, 2]。

nextval 优化： 若 T[next[j]] == T[j]，则失配跳转后仍会与主串当前字符比较并再次失败，可进一步把 nextval[j] = nextval[next[j]]，跳过无效跳转，这是 KMP 的进一步优化。例如上例中，nextval 数组会把部分冗余跳转压缩。

语言实现

以下四种语言均完整实现：求 next（含 nextval 优化）数组 + KMP 匹配，并演示在字符串 "ababaababaa" 中匹配模式串 "ababaa"。Python 额外用 str.find() 和 in 运算符作为内置对比。

说明：教材中 KMP 下标多从 1 开始，而程序语言数组从 0 开始。下面的实现按程序习惯采用 0 下标，next 数组含义做了相应适配，逻辑等价、可直接运行。

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 求 next 数组（0 下标版本）
void get_next(const char *T, int *next) {
    int m = (int)strlen(T);
    int i = 0, j = -1;
    next[0] = -1;              // 约定 next[0] = -1
    while (i < m - 1) {
        if (j == -1 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;       // 注意：这里未做 nextval 优化
        } else {
            j = next[j];
        }
    }
}

// 求 nextval 数组（优化版）
void get_nextval(const char *T, int *nextval) {
    int m = (int)strlen(T);
    int i = 0, j = -1;
    nextval[0] = -1;
    while (i < m - 1) {
        if (j == -1 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j])
                nextval[i] = j;      // 与 next 不同
            else
                nextval[i] = nextval[j];  // 跳过冗余跳转
        } else {
            j = nextval[j];
        }
    }
}

// KMP 匹配：返回 T 在 S 中首次出现的下标，未找到返回 -1
int kmp(const char *S, const char *T, const int *next) {
    int n = (int)strlen(S), m = (int)strlen(T);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];     // 主串 i 不回溯
        }
    }
    if (j == m) return i - m;   // 匹配成功
    return -1;
}

int main() {
    const char *S = "ababaababaa";
    const char *T = "ababaa";
    int m = (int)strlen(T);
    int *next = (int *)malloc(m * sizeof(int));
    int *nextval = (int *)malloc(m * sizeof(int));

    get_next(T, next);
    get_nextval(T, nextval);

    printf("主串: %s\n", S);
    printf("模式串: %s\n", T);
    printf("next 数组: ");
    for (int i = 0; i < m; i++) printf("%d ", next[i]);
    printf("\nnextval 数组: ");
    for (int i = 0; i < m; i++) printf("%d ", nextval[i]);
    printf("\n");

    int pos = kmp(S, T, next);
    printf("KMP 匹配位置: %d\n", pos);   // 期望 4

    free(next);
    free(nextval);
    return 0;
}

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 求 next 数组
void get_next(const string &T, vector<int> &next) {
    int m = T.size();
    int i = 0, j = -1;
    next[0] = -1;
    while (i < m - 1) {
        if (j == -1 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// 求 nextval 数组
void get_nextval(const string &T, vector<int> &nextval) {
    int m = T.size();
    int i = 0, j = -1;
    nextval[0] = -1;
    while (i < m - 1) {
        if (j == -1 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        } else {
            j = nextval[j];
        }
    }
}

// KMP 匹配
int kmp(const string &S, const string &T, const vector<int> &next) {
    int n = S.size(), m = T.size();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    return (j == m) ? i - m : -1;
}

int main() {
    string S = "ababaababaa";
    string T = "ababaa";
    vector<int> next(T.size()), nextval(T.size());
    get_next(T, next);
    get_nextval(T, nextval);

    cout << "主串: " << S << endl;
    cout << "模式串: " << T << endl;
    cout << "next 数组: ";
    for (int x : next) cout << x << " ";
    cout << "\nnextval 数组: ";
    for (int x : nextval) cout << x << " ";
    cout << endl;

    cout << "KMP 匹配位置: " << kmp(S, T, next) << endl;  // 期望 4
    return 0;
}

Java

import java.util.Arrays;

public class KMP {
    // 求 next 数组
    public static int[] getNext(String T) {
        int m = T.length();
        int[] next = new int[m];
        int i = 0, j = -1;
        next[0] = -1;
        while (i < m - 1) {
            if (j == -1 || T.charAt(i) == T.charAt(j)) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    // 求 nextval 数组
    public static int[] getNextVal(String T) {
        int m = T.length();
        int[] nextval = new int[m];
        int i = 0, j = -1;
        nextval[0] = -1;
        while (i < m - 1) {
            if (j == -1 || T.charAt(i) == T.charAt(j)) {
                ++i;
                ++j;
                if (T.charAt(i) != T.charAt(j)) nextval[i] = j;
                else nextval[i] = nextval[j];
            } else {
                j = nextval[j];
            }
        }
        return nextval;
    }

    // KMP 匹配
    public static int kmp(String S, String T, int[] next) {
        int n = S.length(), m = T.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || S.charAt(i) == T.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        return (j == m) ? i - m : -1;
    }

    public static void main(String[] args) {
        String S = "ababaababaa";
        String T = "ababaa";
        int[] next = getNext(T);
        int[] nextval = getNextVal(T);

        System.out.println("主串: " + S);
        System.out.println("模式串: " + T);
        System.out.println("next 数组: " + Arrays.toString(next));
        System.out.println("nextval 数组: " + Arrays.toString(nextval));
        System.out.println("KMP 匹配位置: " + kmp(S, T, next));  // 期望 4
    }
}

Python

def get_next(T: str) -> list:
    """求 next 数组"""
    m = len(T)
    next_arr = [-1] * m
    i, j = 0, -1
    while i < m - 1:
        if j == -1 or T[i] == T[j]:
            i += 1
            j += 1
            next_arr[i] = j
        else:
            j = next_arr[j]
    return next_arr


def get_nextval(T: str) -> list:
    """求 nextval 数组（优化版）"""
    m = len(T)
    nextval = [-1] * m
    i, j = 0, -1
    while i < m - 1:
        if j == -1 or T[i] == T[j]:
            i += 1
            j += 1
            if T[i] != T[j]:
                nextval[i] = j
            else:
                nextval[i] = nextval[j]
        else:
            j = nextval[j]
    return nextval


def kmp(S: str, T: str, next_arr: list) -> int:
    """KMP 匹配，返回首次出现下标，未找到返回 -1"""
    n, m = len(S), len(T)
    i = j = 0
    while i < n and j < m:
        if j == -1 or S[i] == T[j]:
            i += 1
            j += 1
        else:
            j = next_arr[j]
    return i - m if j == m else -1


if __name__ == "__main__":
    S = "ababaababaa"
    T = "ababaa"
    next_arr = get_next(T)
    nextval_arr = get_nextval(T)

    print("主串:", S)
    print("模式串:", T)
    print("next 数组:", next_arr)
    print("nextval 数组:", nextval_arr)
    print("KMP 匹配位置:", kmp(S, T, next_arr))   # 期望 4

    # 内置对比：Python 自带的字符串查找
    print("str.find() 结果:", S.find(T))          # 4
    print("'in' 运算符结果:", T in S)             # True