面试题：C语言字符数组底层原理与高效字符串算法

1. KMP算法原理

KMP（Knuth - Morris - Pratt）算法是一种字符串匹配算法，用于在一个主串 text 中查找一个模式串 pattern。它的核心思想是利用已经匹配的部分信息，避免不必要的字符比较，从而提高匹配效率。

部分匹配表（Partial Match Table）

部分匹配表（也叫前缀函数），对于模式串 pattern 的每个位置 i，记录 pattern 前 i + 1 个字符组成的子串的最长相等前缀和后缀的长度（前缀和后缀不能是整个子串）。例如，对于模式串 "ABABACA"，其部分匹配表为：[0, 0, 1, 2, 3, 0, 1]。

构建部分匹配表的过程如下：

初始化部分匹配表 next 数组，next[0] = 0。
设两个指针 i = 1 和 j = 0，i 用来遍历模式串，j 表示当前已经匹配的前缀长度。
当 i < patternLength 时：
- 如果 pattern[i] == pattern[j]，则 j++，next[i] = j，i++。
- 否则，如果 j > 0，则 j = next[j - 1]，回到上一步继续比较。
- 如果 j == 0，则 next[i] = 0，i++。

2. 代码实现

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

// 构建部分匹配表
void computeLPSArray(char *pattern, int patternLength, int *next) {
    int len = 0;
    next[0] = 0;
    int i = 1;
    while (i < patternLength) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1];
            } else {
                next[i] = len;
                i++;
            }
        }
    }
}

// KMP字符串匹配
int KMPSearch(char *text, char *pattern) {
    int textLength = strlen(text);
    int patternLength = strlen(pattern);
    int *next = (int *)malloc(patternLength * sizeof(int));
    computeLPSArray(pattern, patternLength, next);
    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < textLength) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == patternLength) {
            free(next);
            return i - j;
        } else if (i < textLength && pattern[j] != text[i]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    free(next);
    return -1;
}

3. 时间复杂度和空间复杂度分析

时间复杂度：
- 构建部分匹配表的时间复杂度为 $O(m)$，其中 $m$ 是模式串的长度。
- 匹配过程的时间复杂度为 $O(n)$，其中 $n$ 是主串的长度。
- 因此，整个KMP算法的时间复杂度为 $O(n + m)$。
空间复杂度：
- 需要额外的空间来存储部分匹配表，空间复杂度为 $O(m)$，其中 $m$ 是模式串的长度。

4. 利用字符数组特性优化

减少不必要的内存访问：字符数组在内存中是连续存储的，利用这一特性，在匹配过程中可以减少缓存缺失。例如，在比较字符时，由于连续存储，相邻字符更有可能在同一缓存行中，从而提高访问速度。
利用指针运算：可以使用指针来访问字符数组，指针运算在汇编层面效率更高。在KMP算法实现中，用指针代替数组下标访问，如 *(text + i) 代替 text[i]，虽然现代编译器通常会对此进行优化，但在某些情况下仍能提高性能。

星途面试题库