第 4 章 · 串与数组

串 = 元素为字符的线性表；数组存储有冗余可压缩——分别引出 KMP 与矩阵压缩。

4.1 串的存储

C 串 = '\0' 结尾的 char 数组（见 C 指针第 6 章）；长度用 strlen，不含末尾 '\0'。

4.2 朴素匹配：暴力回溯

// 在 t 中找 p 首次出现，返回下标，找不到返回 -1
int naive(char *t, char *p) {
    int n = strlen(t), m = strlen(p);
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && t[i + j] == p[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

最坏 O(n·m)：如 t = "aaaaa...b"、p = "aaaab"，每次匹配到最后一个字符才失败，主串指针还要回退。

4.3 KMP：利用已匹配信息不回退

朴素失败后 i 回退重扫。KMP 观察到失败前已匹配的 p[0..j-1] 中，其「最长相等前后缀」可以直接对齐，i 不回退。next[j] = 子串 p[0..j-1] 的最长相等前后缀长度。

void get_next(char *p, int *next) {
    int m = strlen(p);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < m - 1) {
        if (j == -1 || p[i] == p[j]) next[++i] = ++j;
        else j = next[j];
    }
}

int kmp(char *t, char *p) {
    int n = strlen(t), m = strlen(p);
    int *next = malloc(m * sizeof(int));
    if (!next) return -1;
    get_next(p, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || t[i] == p[j]) { i++; j++; }
        else j = next[j];
    }
    free(next);
    return j == m ? i - j : -1;
}

KMP 全程 O(n+m)：主串指针不回退，next 数组 O(m) 预处理。

4.4 特殊矩阵压缩

矩阵元素分布有规律时，不必存满 n² 个，只存「非零/非重复」部分并给出下标映射。

矩阵	存什么	元素个数	下标映射（行优先，i≥j）
对称	下三角（或上三角）	n(n+1)/2	k = i(i+1)/2 + j
三角	三角区 + 对角	n(n+1)/2	同上
稀疏	只存三元组 (i,j,v)	非零元数 t	顺序表或十字链表

对称矩阵 A[i][j] = A[j][i]，只存下三角，读 A[i][j]（i < j）时转成 A[j][i]。稀疏矩阵用三元组表省下大量零元素存储。

// 下三角按行优先存入一维数组，取 A[i][j]（i>=j 为有效元素）
int sym_get(int *b, int i, int j) {
    if (i < j) { int t = i; i = j; j = t; }   // 利用对称性
    return b[i * (i + 1) / 2 + j];
}

对比：朴素最坏 O(n·m) 但实现简单；KMP O(n+m) 需预计算 next。短串/一次性用朴素，长文本反复用 KMP（另有 BM、Sunday）。

对比：对称/三角靠规律省一半、下标映射 O(1)；稀疏只存非零省更多，但丢随机访问（三元组扫 O(t)）。