这是本节的多页打印视图。点击此处打印.

字符串

本章可能在选择题中出现，掌握KMP算法的思想，能够手工模拟KMP过程即可。

1: 定义和实现
2: 模式匹配

1 - 定义和实现

了解字符串的不同存储结构和基本操作即可，一般不会直接考察。

串的定义

字符串是计算机科学中的一个基本概念，通常被定义为有限序列中字符的有序集合。

形式定义：

字符串 $S$ 时字符集 $\Sigma$ 上的一个有限序列：$S = a_1 a_2 \cdots a_n$，其中 $a_i \in \Sigma$，且 $n$ 为字符串的长度，当 $n = 0$ 时，称为空字符串。

串的存储结构

1. 定长顺序存储表示

在定长顺序存储表示中，每个字符串都有固定的长度，通常用一个预定义的最大大小来表示。这种表示方法使用一个一维数组，数组的大小等于预定的最大长度。

在某些语境中（例如C语言），使用特殊字符（如 '\0'）来标识字符串结束。

#define MAX_SIZE 100 // 预定义的最大大小

typedef struct {
    char data[MAX_SIZE];  // 字符数组
    int length;           // 当前字符串的长度
} FixedString;

2. 堆分配存储表示

在堆分配存储表示中，每个字符串具有其自己的长度，因此可以动态地分配存储空间。字符串在堆中分配空间，只需要那么多的空间来存储实际的字符以及结束字符或长度信息。

typedef struct {
    char *data;           // 指向动态分配空间的指针
    int length;           // 字符串的长度
} HeapString;

// 创建一个新的字符串
void initHeapString(HeapString *s, const char *str) {
    s->length = strlen(str);
    s->data = (char *)malloc((s->length + 1) * sizeof(char));
    if (s->data == NULL) {
        exit(1);  // 分配失败
    }
    strcpy(s->data, str);
}

// 释放字符串
void freeHeapString(HeapString *s) {
    free(s->data);
    s->length = 0;
}

3. 块链存储表示

块链存储表示是结合了链表与块存储的思想。串分为较小的块，每个块存储一部分字符。块之间使用指针链接。这样，整个字符串就变成了一个字符块的链表。

#define BLOCK_SIZE 4 // 为了简单起见，设块大小为4

typedef struct StringBlock {
    char data[BLOCK_SIZE];   // 块中的字符数据
    struct StringBlock *next;  // 指向下一个块的指针
} StringBlock;

typedef struct {
    StringBlock *head;      // 指向第一个块的指针
    int length;             // 字符串的总长度
} BlockString;

// 初始化块链字符串
void initBlockString(BlockString *s) {
    s->head = NULL;
    s->length = 0;
}

// 为了简化，这里只展示了数据结构定义和初始化函数。实际应用中还需要考虑其他函数，如插入、删除、销毁等。

串的基本操作

赋值（Assign）：
- 将一个串的内容复制到另一个串。
比较（Compare）：
- 根据字符的字典顺序比较两个串。可以判断两个串是否相等，或者一个串是否小于或大于另一个串。
长度（Length）：
- 返回串的长度，即串中字符的数目。
连接（Concat）：
- 将两个串连接成一个新的串。例如，将串"Hello"和串"World"连接为"HelloWorld"。
子串提取（Substr）：
- 从串中提取某个指定位置开始的指定长度的字符序列作为一个新的串。例如，从串"HelloWorld"中提取从位置1开始的5个字符，得到"Hello"。
插入（Insert）：
- 在串的指定位置插入另一个串。例如，在串"HelloWorld"的第6个位置插入串"Beautiful", 得到"HelloBeautifulWorld"。
删除（Delete）：
- 从串中删除从指定位置开始的指定长度的字符。
替换（Subsititude）：
- 将串中某个子串的所有出现替换为另一个子串。例如，将串"apple, banana, apple"中的"apple"替换为"orange"，得到"orange, banana, orange"。
模式匹配（Index）：
- 在串中查找另一个子串的位置。这通常使用算法如KMP、BM或Sunday来加速查找。
清空（Clear）：
- 释放串的存储空间并将其设置为空串。

2 - 模式匹配

需熟练掌握KMP算法，包含next数组的计算，以及手工模拟主串和模式串的移动过程，可能在选择题中考察。

字符串模式匹配是计算机科学中的基础问题，主要是在一个主字符串中查找一个子字符串模式。

简单模式匹配算法

简单模式匹配算法通常指的是暴力方法（或称为朴素算法），其基本思想是逐个检查主字符串的每一个位置是否开始与子字符串匹配。

算法描述：

从主字符串的第一个字符开始匹配。
如果第一个字符匹配，那么匹配下一个字符，依此类推。
如果在任何时刻字符不匹配，重新从主字符串的下一个字符开始匹配。
如果子字符串完全匹配，返回主字符串中的开始位置。
如果到达主字符串的末尾都没有完全匹配的子字符串，则返回-1。

int simplePatternMatching(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    // 如果主字符串的长度小于模式字符串的长度，直接返回-1
    if (m < n) return -1;

    for (int i = 0; i <= m - n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (mainStr[i + j] != pattern[j]) {
                break;
            }
        }
        // 如果j等于模式串的长度，说明已经找到匹配
        if (j == n) return i;
    }
    return -1;  // 没有找到匹配
}

这个简单模式匹配算法的时间复杂度是 $O(mn)$ ，其中 $m$ 是主字符串的长度， $n$ 是模式字符串的长度。

KMP算法

与简单模式匹配算法不同，KMP算法在发现不匹配的字符时能够避免不必要的比较，从而提高效率。

基本原理：

简单模式匹配时间复杂度过高，因为每一次匹配失败都得从下一个位置重新开始。这就没有充分应用模式串的特性，比如对于字符串 abcdabc，我们可以发现：

其前缀包含a, ab, abc, abcd等
起后缀包含c, bc, abc, dabc等

abc是在其前缀和后缀中都包含的部分，在字符串匹配时，我们可以充分利用该信息，匹配失败时，我们可以不用从下一个位置开始，而是从模式串内部的某个位置开始。

KMP算法就是基于这个思想，其核心是一个称为“部分匹配表”或“前缀函数”的辅助数组（通常称为next数组），该数组用于确定当模式串与主串不匹配时应该如何有效地移动模式串。

算法描述：

根据模式串计算next数组。
使用next数组，对主串和模式串进行比较。
在发现不匹配的情况下，利用next数组调整模式串的位置。

next数组计算

next数组的计算方式如下：

$$next[j] = \begin{cases} 0 &\text{if } j = 1 \\ max\{k \text{ | } 1 \lt k \lt j\ \text{ and }\ p_1 \cdots p_{k} = p_{j-k+1} \cdots p_{j}\} &\text{if k exists}\\ 0 &\text{if k not exists} \end{cases}$$

如果模式串为pattern，用通俗的话来说，next[j]就是字串pattern[0:k]（pattern的前k个字符构成的子串）的最长相同前缀和后缀的长度。

根据next数组调整位置

用i表示主串当前下标，用j表示模式串当前下标：

如果main[i] == pattern[j]，将i和j向后向后移动一位。
如果main[i] != pattern[j]：
- 如果j == 0，将i向后移动一位。
- 如果j != 0，将j移动到next[j-1]。

以下图为例，说明主串 “ababcabcabababd” 和模式串 “ababd” 的匹配过程。

void computeNextArray(const char* pattern, int m, int* next) {
    int len = 0;
    next[0] = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
}

int KMP(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    int next[n];
    computeNextArray(pattern, n, next);

    int i = 0, j = 0;
    while (i < m) {
        if (pattern[j] == mainStr[i]) {
            i++;
            j++;
        }

        if (j == n) {
            return i - j;
        } else if (i < m && pattern[j] != mainStr[i]) {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
    }

    return -1; // 没有找到匹配
}

字符串