第4章 串代码
使用建议
- 先配合对应章节阅读：第4章 串 正文
- 这一页优先提供站内可直接查看的代码版本，适合网页阅读和搜索。
- 这一页主要用于网页阅读，建议结合对应正文与逐行注释版一起使用。
文件位置
- 普通代码版：
第4章普通代码版
- 逐行注释版：
第4章逐行注释版代码
- 兼容编码版：
第4章兼容编码版逐行注释代码
普通代码版
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STR_LEN 255
/* 定长顺序串：字符放在连续数组里，length 记录实际串长。 */
typedef struct {
char ch[MAX_STR_LEN + 1];
int length;
} SString;
/* 堆分配串：字符空间动态申请，更适合长度不固定的场景。 */
typedef struct {
char *ch;
int length;
} HString;
/* 初始化定长顺序串为空串。 */
void InitSString(SString *str) {
if (str == NULL) {
return;
}
str->ch[0] = '\0';
str->length = 0;
}
/* 给定长顺序串赋值，长度超出上限时进行截断。 */
bool StrAssignSString(SString *str, const char *chars) {
size_t len;
if (str == NULL || chars == NULL) {
return false;
}
len = strlen(chars);
if (len > MAX_STR_LEN) {
len = MAX_STR_LEN;
}
memcpy(str->ch, chars, len);
str->ch[len] = '\0';
str->length = (int)len;
return true;
}
/* 复制定长顺序串。 */
bool StrCopySString(SString *target, const SString *source) {
if (target == NULL || source == NULL) {
return false;
}
memcpy(target->ch, source->ch, (size_t)source->length + 1);
target->length = source->length;
return true;
}
/* 判断定长顺序串是否为空。 */
bool StrEmptySString(const SString *str) {
return str == NULL || str->length == 0;
}
/* 比较两个定长顺序串的大小，规则与字典序一致。 */
int StrCompareSString(const SString *left, const SString *right) {
int i;
int limit;
if (left == NULL || right == NULL) {
return 0;
}
limit = (left->length < right->length) ? left->length : right->length;
for (i = 0; i < limit; i++) {
if (left->ch[i] != right->ch[i]) {
return (unsigned char)left->ch[i] - (unsigned char)right->ch[i];
}
}
return left->length - right->length;
}
/* 返回定长顺序串长度。 */
int StrLengthSString(const SString *str) {
return (str == NULL) ? 0 : str->length;
}
/* 取子串：从 1-based 的 pos 开始，长度为 len。 */
bool SubStringSString(SString *sub, const SString *source, int pos, int len) {
if (sub == NULL || source == NULL || pos < 1 || len < 0) {
return false;
}
if (pos > source->length || pos + len - 1 > source->length) {
return false;
}
memcpy(sub->ch, source->ch + pos - 1, (size_t)len);
sub->ch[len] = '\0';
sub->length = len;
return true;
}
/* 串联接：把 left 和 right 接成一个新串，必要时截断。 */
bool ConcatSString(SString *result, const SString *left, const SString *right) {
int copy_right;
if (result == NULL || left == NULL || right == NULL) {
return false;
}
memcpy(result->ch, left->ch, (size_t)left->length);
copy_right = right->length;
if (left->length + right->length > MAX_STR_LEN) {
copy_right = MAX_STR_LEN - left->length;
}
memcpy(result->ch + left->length, right->ch, (size_t)copy_right);
result->length = left->length + copy_right;
result->ch[result->length] = '\0';
return true;
}
/* 清空定长顺序串。 */
void ClearStringSString(SString *str) {
if (str == NULL) {
return;
}
str->ch[0] = '\0';
str->length = 0;
}
/* 打印定长顺序串，方便观察当前串值和串长。 */
void PrintSString(const SString *str) {
if (str == NULL) {
return;
}
printf("\"%s\" length=%d\n", str->ch, str->length);
}
/* 初始化堆分配串为空。 */
void InitHString(HString *str) {
if (str == NULL) {
return;
}
str->ch = NULL;
str->length = 0;
}
/* 给堆分配串赋值，按实际长度动态申请空间。 */
bool StrAssignHString(HString *str, const char *chars) {
size_t len;
char *buffer;
if (str == NULL || chars == NULL) {
return false;
}
len = strlen(chars);
buffer = (char *)malloc(len + 1);
if (buffer == NULL) {
return false;
}
memcpy(buffer, chars, len + 1);
free(str->ch);
str->ch = buffer;
str->length = (int)len;
return true;
}
/* 销毁堆分配串。 */
void DestroyHString(HString *str) {
if (str == NULL) {
return;
}
free(str->ch);
str->ch = NULL;
str->length = 0;
}
/* 朴素模式匹配：返回模式串在主串中首次出现的 1-based 位置，不存在则返回 0。 */
int IndexBF(const SString *main_str, const SString *pattern) {
int i = 1;
int j = 1;
if (main_str == NULL || pattern == NULL || pattern->length == 0) {
return 0;
}
while (i <= main_str->length && j <= pattern->length) {
if (main_str->ch[i - 1] == pattern->ch[j - 1]) {
i++;
j++;
} else {
i = i - j + 2; /* 主串回到本趟起点的下一位。 */
j = 1; /* 模式串重新从头开始。 */
}
}
if (j > pattern->length) {
return i - pattern->length;
}
return 0;
}
/* 计算模式串的 next 数组，采用教材常见的 1-based 含义。 */
bool GetNextArray(const SString *pattern, int *next) {
int i = 1;
int j = 0;
if (pattern == NULL || next == NULL || pattern->length <= 0) {
return false;
}
next[1] = 0;
while (i < pattern->length) {
if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return true;
}
/* 计算改进后的 nextval 数组，避免某些无意义比较。 */
bool GetNextValArray(const SString *pattern, int *nextval) {
int i = 1;
int j = 0;
if (pattern == NULL || nextval == NULL || pattern->length <= 0) {
return false;
}
nextval[1] = 0;
while (i < pattern->length) {
if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
i++;
j++;
if (pattern->ch[i - 1] != pattern->ch[j - 1]) {
nextval[i] = j;
} else {
nextval[i] = nextval[j];
}
} else {
j = nextval[j];
}
}
return true;
}
/* KMP 模式匹配：主串指针不回溯，返回首次匹配的 1-based 位置。 */
int IndexKMP(const SString *main_str, const SString *pattern, const int *next) {
int i = 1;
int j = 1;
if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
return 0;
}
while (i <= main_str->length && j <= pattern->length) {
if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j > pattern->length) {
return i - pattern->length;
}
return 0;
}
/* 统计模式串在主串中不重叠匹配的次数，适合演示“匹配成功后继续向后找”的写法。 */
int CountPatternMatchesNonOverlapping(const SString *main_str, const SString *pattern, const int *next) {
int i = 1;
int j = 1;
int count = 0;
if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
return 0;
}
while (i <= main_str->length) {
if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
i++;
j++;
if (j > pattern->length) {
count++;
j = next[pattern->length];
}
} else {
j = next[j];
}
}
return count;
}
/* 统计模式串在主串中允许重叠出现的次数，便于和上面的“不重叠统计”做对比。 */
int CountPatternMatchesOverlappingBF(const SString *main_str, const SString *pattern) {
int start;
int j;
int count = 0;
if (main_str == NULL || pattern == NULL || pattern->length == 0) {
return 0;
}
for (start = 0; start <= main_str->length - pattern->length; start++) {
for (j = 0; j < pattern->length; j++) {
if (main_str->ch[start + j] != pattern->ch[j]) {
break;
}
}
if (j == pattern->length) {
count++;
}
}
return count;
}
/* 打印 next/nextval 数组，方便观察 KMP 预处理结果。 */
void PrintIntArray1Based(const int *arr, int length, const char *name) {
int i;
if (arr == NULL || name == NULL) {
return;
}
printf("%s = [", name);
for (i = 1; i <= length; i++) {
if (i > 1) {
printf(", ");
}
printf("%d", arr[i]);
}
printf("]\n");
}
int main(void) {
SString main_str;
SString pattern;
SString left;
SString right;
SString concat_result;
SString sub;
HString heap_str;
int next[MAX_STR_LEN + 1] = {0};
int nextval[MAX_STR_LEN + 1] = {0};
int position_bf;
int position_kmp;
int match_count;
InitSString(&main_str);
InitSString(&pattern);
InitSString(&left);
InitSString(&right);
InitSString(&concat_result);
InitSString(&sub);
InitHString(&heap_str);
StrAssignSString(&main_str, "ababcabcacbab");
StrAssignSString(&pattern, "abcac");
StrAssignSString(&left, "China");
StrAssignSString(&right, "Beijing");
PrintSString(&main_str);
PrintSString(&pattern);
if (SubStringSString(&sub, &main_str, 3, 5)) {
PrintSString(&sub);
}
ConcatSString(&concat_result, &left, &right);
PrintSString(&concat_result);
printf("compare left vs right: %d\n", StrCompareSString(&left, &right));
printf("main length: %d\n", StrLengthSString(&main_str));
printf("pattern empty: %s\n", StrEmptySString(&pattern) ? "true" : "false");
position_bf = IndexBF(&main_str, &pattern);
printf("BF first match position: %d\n", position_bf);
if (GetNextArray(&pattern, next)) {
PrintIntArray1Based(next, pattern.length, "next");
}
if (GetNextValArray(&pattern, nextval)) {
PrintIntArray1Based(nextval, pattern.length, "nextval");
}
position_kmp = IndexKMP(&main_str, &pattern, next);
printf("KMP first match position: %d\n", position_kmp);
StrAssignSString(&main_str, "aabaabaabaac");
StrAssignSString(&pattern, "aabaac");
GetNextArray(&pattern, next);
PrintSString(&main_str);
PrintSString(&pattern);
PrintIntArray1Based(next, pattern.length, "next");
printf("KMP first match position: %d\n", IndexKMP(&main_str, &pattern, next));
StrAssignSString(&main_str, "aaaaa");
StrAssignSString(&pattern, "aa");
GetNextArray(&pattern, next);
match_count = CountPatternMatchesNonOverlapping(&main_str, &pattern, next);
printf("non-overlapping match count in \"aaaaa\" for \"aa\": %d\n", match_count);
printf("overlapping match count in \"aaaaa\" for \"aa\": %d\n",
CountPatternMatchesOverlappingBF(&main_str, &pattern));
if (StrAssignHString(&heap_str, "dynamic string example")) {
printf("heap string: \"%s\" length=%d\n", heap_str.ch, heap_str.length);
}
DestroyHString(&heap_str);
return 0;
}
逐行注释版
/* 第 1 行注释：本行引入头文件，为后面的类型、函数和库接口提供声明。 */
#include <stdbool.h>
/* 第 2 行注释：本行引入头文件，为后面的类型、函数和库接口提供声明。 */
#include <stdio.h>
/* 第 3 行注释：本行引入头文件，为后面的类型、函数和库接口提供声明。 */
#include <stdlib.h>
/* 第 4 行注释：本行引入头文件，为后面的类型、函数和库接口提供声明。 */
#include <string.h>
/* 第 5 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 6 行注释：本行定义宏常量，统一管理本章字符串实现会用到的固定上限。 */
#define MAX_STR_LEN 255
/* 第 7 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 8 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 定长顺序串：字符放在连续数组里，length 记录实际串长。 */
/* 第 9 行注释：本行开始定义结构体类型，用来把一组相关数据打包成一个整体。 */
typedef struct {
/* 第 10 行注释：本行定义字符数组，用连续空间保存串内容，并预留结尾标记位置。 */
char ch[MAX_STR_LEN + 1];
/* 第 11 行注释：本行定义长度字段，用来记录当前串实际保存了多少个字符。 */
int length;
/* 第 12 行注释：本行结束顺序串结构体定义，后面就可以用 SString 表示定长顺序串。 */
} SString;
/* 第 13 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 14 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 堆分配串：字符空间动态申请，更适合长度不固定的场景。 */
/* 第 15 行注释：本行开始定义结构体类型，用来把一组相关数据打包成一个整体。 */
typedef struct {
/* 第 16 行注释：本行定义字符指针，让堆分配串能够指向动态申请出来的存储区。 */
char *ch;
/* 第 17 行注释：本行定义长度字段，用来记录当前串实际保存了多少个字符。 */
int length;
/* 第 18 行注释：本行结束堆分配串结构体定义，后面就可以用 HString 表示动态串。 */
} HString;
/* 第 19 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 20 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 初始化定长顺序串为空串。 */
/* 第 21 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void InitSString(SString *str) {
/* 第 22 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL) {
/* 第 23 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 24 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 25 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch[0] = '\0';
/* 第 26 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = 0;
/* 第 27 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 28 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 29 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 给定长顺序串赋值，长度超出上限时进行截断。 */
/* 第 30 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool StrAssignSString(SString *str, const char *chars) {
/* 第 31 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
size_t len;
/* 第 32 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 33 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL || chars == NULL) {
/* 第 34 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 35 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 36 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 37 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
len = strlen(chars);
/* 第 38 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (len > MAX_STR_LEN) {
/* 第 39 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
len = MAX_STR_LEN;
/* 第 40 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 41 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(str->ch, chars, len);
/* 第 42 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch[len] = '\0';
/* 第 43 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = (int)len;
/* 第 44 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 45 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 46 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 47 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 复制定长顺序串。 */
/* 第 48 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool StrCopySString(SString *target, const SString *source) {
/* 第 49 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (target == NULL || source == NULL) {
/* 第 50 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 51 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 52 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(target->ch, source->ch, (size_t)source->length + 1);
/* 第 53 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
target->length = source->length;
/* 第 54 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 55 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 56 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 57 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 判断定长顺序串是否为空。 */
/* 第 58 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool StrEmptySString(const SString *str) {
/* 第 59 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return str == NULL || str->length == 0;
/* 第 60 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 61 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 62 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 比较两个定长顺序串的大小，规则与字典序一致。 */
/* 第 63 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int StrCompareSString(const SString *left, const SString *right) {
/* 第 64 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i;
/* 第 65 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int limit;
/* 第 66 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 67 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (left == NULL || right == NULL) {
/* 第 68 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 69 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 70 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 71 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
limit = (left->length < right->length) ? left->length : right->length;
/* 第 72 行注释：本行开始计数循环，常用于按顺序扫描字符或数组元素。 */
for (i = 0; i < limit; i++) {
/* 第 73 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (left->ch[i] != right->ch[i]) {
/* 第 74 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return (unsigned char)left->ch[i] - (unsigned char)right->ch[i];
/* 第 75 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 76 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 77 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return left->length - right->length;
/* 第 78 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 79 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 80 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 返回定长顺序串长度。 */
/* 第 81 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int StrLengthSString(const SString *str) {
/* 第 82 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return (str == NULL) ? 0 : str->length;
/* 第 83 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 84 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 85 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 取子串：从 1-based 的 pos 开始，长度为 len。 */
/* 第 86 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool SubStringSString(SString *sub, const SString *source, int pos, int len) {
/* 第 87 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (sub == NULL || source == NULL || pos < 1 || len < 0) {
/* 第 88 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 89 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 90 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (pos > source->length || pos + len - 1 > source->length) {
/* 第 91 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 92 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 93 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 94 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(sub->ch, source->ch + pos - 1, (size_t)len);
/* 第 95 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
sub->ch[len] = '\0';
/* 第 96 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
sub->length = len;
/* 第 97 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 98 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 99 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 100 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 串联接：把 left 和 right 接成一个新串，必要时截断。 */
/* 第 101 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool ConcatSString(SString *result, const SString *left, const SString *right) {
/* 第 102 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int copy_right;
/* 第 103 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 104 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (result == NULL || left == NULL || right == NULL) {
/* 第 105 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 106 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 107 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 108 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(result->ch, left->ch, (size_t)left->length);
/* 第 109 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
copy_right = right->length;
/* 第 110 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (left->length + right->length > MAX_STR_LEN) {
/* 第 111 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
copy_right = MAX_STR_LEN - left->length;
/* 第 112 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 113 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(result->ch + left->length, right->ch, (size_t)copy_right);
/* 第 114 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
result->length = left->length + copy_right;
/* 第 115 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
result->ch[result->length] = '\0';
/* 第 116 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 117 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 118 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 119 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 清空定长顺序串。 */
/* 第 120 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void ClearStringSString(SString *str) {
/* 第 121 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL) {
/* 第 122 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 123 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 124 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch[0] = '\0';
/* 第 125 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = 0;
/* 第 126 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 127 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 128 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 打印定长顺序串，方便观察当前串值和串长。 */
/* 第 129 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void PrintSString(const SString *str) {
/* 第 130 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL) {
/* 第 131 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 132 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 133 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("\"%s\" length=%d\n", str->ch, str->length);
/* 第 134 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 135 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 136 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 初始化堆分配串为空。 */
/* 第 137 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void InitHString(HString *str) {
/* 第 138 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL) {
/* 第 139 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 140 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 141 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch = NULL;
/* 第 142 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = 0;
/* 第 143 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 144 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 145 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 给堆分配串赋值，按实际长度动态申请空间。 */
/* 第 146 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool StrAssignHString(HString *str, const char *chars) {
/* 第 147 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
size_t len;
/* 第 148 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
char *buffer;
/* 第 149 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 150 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL || chars == NULL) {
/* 第 151 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 152 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 153 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 154 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
len = strlen(chars);
/* 第 155 行注释：本行动态申请内存，让字符串长度可以按实际需要灵活扩展。 */
buffer = (char *)malloc(len + 1);
/* 第 156 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (buffer == NULL) {
/* 第 157 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 158 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 159 行注释：本行执行整段内存复制，把一批连续字符一次性拷贝到目标位置。 */
memcpy(buffer, chars, len + 1);
/* 第 160 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 161 行注释：本行释放之前动态申请的内存，避免程序产生内存泄漏。 */
free(str->ch);
/* 第 162 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch = buffer;
/* 第 163 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = (int)len;
/* 第 164 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 165 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 166 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 167 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 销毁堆分配串。 */
/* 第 168 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void DestroyHString(HString *str) {
/* 第 169 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (str == NULL) {
/* 第 170 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 171 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 172 行注释：本行释放之前动态申请的内存，避免程序产生内存泄漏。 */
free(str->ch);
/* 第 173 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->ch = NULL;
/* 第 174 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
str->length = 0;
/* 第 175 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 176 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 177 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 朴素模式匹配：返回模式串在主串中首次出现的 1-based 位置，不存在则返回 0。 */
/* 第 178 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int IndexBF(const SString *main_str, const SString *pattern) {
/* 第 179 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i = 1;
/* 第 180 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j = 1;
/* 第 181 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 182 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str == NULL || pattern == NULL || pattern->length == 0) {
/* 第 183 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 184 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 185 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 186 行注释：本行开始循环，只要条件成立，就会反复执行后面的代码块。 */
while (i <= main_str->length && j <= pattern->length) {
/* 第 187 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str->ch[i - 1] == pattern->ch[j - 1]) {
/* 第 188 行注释：本行让主指针向后移动一位，表示当前比较已经处理完毕。 */
i++;
/* 第 189 行注释：本行让模式串相关指针向后移动一位，继续尝试扩展已有匹配。 */
j++;
/* 第 190 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 191 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
i = i - j + 2; /* 主串回到本趟起点的下一位。 */
/* 第 192 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
j = 1; /* 模式串重新从头开始。 */
/* 第 193 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 194 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 195 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 196 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j > pattern->length) {
/* 第 197 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return i - pattern->length;
/* 第 198 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 199 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 200 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 201 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 202 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 计算模式串的 next 数组，采用教材常见的 1-based 含义。 */
/* 第 203 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool GetNextArray(const SString *pattern, int *next) {
/* 第 204 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i = 1;
/* 第 205 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j = 0;
/* 第 206 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 207 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (pattern == NULL || next == NULL || pattern->length <= 0) {
/* 第 208 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 209 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 210 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 211 行注释：本行给 next 数组的首元素赋初值，表示第一个字符失配时只能重新起步。 */
next[1] = 0;
/* 第 212 行注释：本行开始循环，只要条件成立，就会反复执行后面的代码块。 */
while (i < pattern->length) {
/* 第 213 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
/* 第 214 行注释：本行让主指针向后移动一位，表示当前比较已经处理完毕。 */
i++;
/* 第 215 行注释：本行让模式串相关指针向后移动一位，继续尝试扩展已有匹配。 */
j++;
/* 第 216 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
next[i] = j;
/* 第 217 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 218 行注释：本行按 next 数组回跳，失配后不重头开始，而是复用已有结构信息。 */
j = next[j];
/* 第 219 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 220 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 221 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 222 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 223 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 224 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 计算改进后的 nextval 数组，避免某些无意义比较。 */
/* 第 225 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
bool GetNextValArray(const SString *pattern, int *nextval) {
/* 第 226 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i = 1;
/* 第 227 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j = 0;
/* 第 228 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 229 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (pattern == NULL || nextval == NULL || pattern->length <= 0) {
/* 第 230 行注释：本行返回失败结果，用来告诉调用者这次操作没有成功完成。 */
return false;
/* 第 231 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 232 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 233 行注释：本行给 nextval 数组的首元素赋初值，含义与 next[1] 类似。 */
nextval[1] = 0;
/* 第 234 行注释：本行开始循环，只要条件成立，就会反复执行后面的代码块。 */
while (i < pattern->length) {
/* 第 235 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j == 0 || pattern->ch[i - 1] == pattern->ch[j - 1]) {
/* 第 236 行注释：本行让主指针向后移动一位，表示当前比较已经处理完毕。 */
i++;
/* 第 237 行注释：本行让模式串相关指针向后移动一位，继续尝试扩展已有匹配。 */
j++;
/* 第 238 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (pattern->ch[i - 1] != pattern->ch[j - 1]) {
/* 第 239 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
nextval[i] = j;
/* 第 240 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 241 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
nextval[i] = nextval[j];
/* 第 242 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 243 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 244 行注释：本行按 nextval 数组回跳，尽量跳过那些注定仍会失配的位置。 */
j = nextval[j];
/* 第 245 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 246 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 247 行注释：本行返回成功结果，用来告诉调用者当前操作已经正确完成。 */
return true;
/* 第 248 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 249 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 250 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* KMP 模式匹配：主串指针不回溯，返回首次匹配的 1-based 位置。 */
/* 第 251 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int IndexKMP(const SString *main_str, const SString *pattern, const int *next) {
/* 第 252 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i = 1;
/* 第 253 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j = 1;
/* 第 254 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 255 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
/* 第 256 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 257 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 258 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 259 行注释：本行开始循环，只要条件成立，就会反复执行后面的代码块。 */
while (i <= main_str->length && j <= pattern->length) {
/* 第 260 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
/* 第 261 行注释：本行让主指针向后移动一位，表示当前比较已经处理完毕。 */
i++;
/* 第 262 行注释：本行让模式串相关指针向后移动一位，继续尝试扩展已有匹配。 */
j++;
/* 第 263 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 264 行注释：本行按 next 数组回跳，失配后不重头开始，而是复用已有结构信息。 */
j = next[j];
/* 第 265 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 266 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 267 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 268 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j > pattern->length) {
/* 第 269 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return i - pattern->length;
/* 第 270 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 271 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 272 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 273 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 274 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 统计模式串在主串中不重叠匹配的次数，适合演示“匹配成功后继续向后找”的写法。 */
/* 第 275 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int CountPatternMatchesNonOverlapping(const SString *main_str, const SString *pattern, const int *next) {
/* 第 276 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i = 1;
/* 第 277 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j = 1;
/* 第 278 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int count = 0;
/* 第 279 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 280 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str == NULL || pattern == NULL || next == NULL || pattern->length == 0) {
/* 第 281 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 282 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 283 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 284 行注释：本行开始循环，只要条件成立，就会反复执行后面的代码块。 */
while (i <= main_str->length) {
/* 第 285 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j == 0 || main_str->ch[i - 1] == pattern->ch[j - 1]) {
/* 第 286 行注释：本行让主指针向后移动一位，表示当前比较已经处理完毕。 */
i++;
/* 第 287 行注释：本行让模式串相关指针向后移动一位，继续尝试扩展已有匹配。 */
j++;
/* 第 288 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j > pattern->length) {
/* 第 289 行注释：本行把匹配次数加一，说明程序刚刚确认找到了一次完整匹配。 */
count++;
/* 第 290 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
j = next[pattern->length];
/* 第 291 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 292 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
} else {
/* 第 293 行注释：本行按 next 数组回跳，失配后不重头开始，而是复用已有结构信息。 */
j = next[j];
/* 第 294 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 295 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 296 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return count;
/* 第 297 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 298 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 299 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 统计模式串在主串中允许重叠出现的次数，便于和上面的“不重叠统计”做对比。 */
/* 第 300 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int CountPatternMatchesOverlappingBF(const SString *main_str, const SString *pattern) {
/* 第 301 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int start;
/* 第 302 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int j;
/* 第 303 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int count = 0;
/* 第 304 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 305 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str == NULL || pattern == NULL || pattern->length == 0) {
/* 第 306 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 307 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 308 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 309 行注释：本行开始计数循环，常用于按顺序扫描字符或数组元素。 */
for (start = 0; start <= main_str->length - pattern->length; start++) {
/* 第 310 行注释：本行开始计数循环，常用于按顺序扫描字符或数组元素。 */
for (j = 0; j < pattern->length; j++) {
/* 第 311 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (main_str->ch[start + j] != pattern->ch[j]) {
/* 第 312 行注释：本行立即跳出当前循环，因为后续语句对这一轮已经没有必要继续执行。 */
break;
/* 第 313 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 314 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 315 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (j == pattern->length) {
/* 第 316 行注释：本行把匹配次数加一，说明程序刚刚确认找到了一次完整匹配。 */
count++;
/* 第 317 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 318 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 319 行注释：本行返回计算结果，把函数最终得到的值交还给调用者。 */
return count;
/* 第 320 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 321 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 322 行注释：本行本身就是原始注释，它用于概括下面那段代码的核心作用。 */
/* 打印 next/nextval 数组，方便观察 KMP 预处理结果。 */
/* 第 323 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
void PrintIntArray1Based(const int *arr, int length, const char *name) {
/* 第 324 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int i;
/* 第 325 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 326 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (arr == NULL || name == NULL) {
/* 第 327 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
return;
/* 第 328 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 329 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 330 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("%s = [", name);
/* 第 331 行注释：本行开始计数循环，常用于按顺序扫描字符或数组元素。 */
for (i = 1; i <= length; i++) {
/* 第 332 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (i > 1) {
/* 第 333 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf(", ");
/* 第 334 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 335 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("%d", arr[i]);
/* 第 336 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 337 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("]\n");
/* 第 338 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 339 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 340 行注释：本行开始定义一个函数，后面的代码块会实现这个函数的完整逻辑。 */
int main(void) {
/* 第 341 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString main_str;
/* 第 342 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString pattern;
/* 第 343 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString left;
/* 第 344 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString right;
/* 第 345 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString concat_result;
/* 第 346 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
SString sub;
/* 第 347 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
HString heap_str;
/* 第 348 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int next[MAX_STR_LEN + 1] = {0};
/* 第 349 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int nextval[MAX_STR_LEN + 1] = {0};
/* 第 350 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int position_bf;
/* 第 351 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int position_kmp;
/* 第 352 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
int match_count;
/* 第 353 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 354 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&main_str);
/* 第 355 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&pattern);
/* 第 356 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&left);
/* 第 357 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&right);
/* 第 358 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&concat_result);
/* 第 359 行注释：本行调用顺序串初始化函数，把对应变量先置成干净可用的状态。 */
InitSString(&sub);
/* 第 360 行注释：本行调用堆串初始化函数，避免后面直接使用野指针。 */
InitHString(&heap_str);
/* 第 361 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 362 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&main_str, "ababcabcacbab");
/* 第 363 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&pattern, "abcac");
/* 第 364 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&left, "China");
/* 第 365 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&right, "Beijing");
/* 第 366 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 367 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&main_str);
/* 第 368 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&pattern);
/* 第 369 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 370 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (SubStringSString(&sub, &main_str, 3, 5)) {
/* 第 371 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&sub);
/* 第 372 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 373 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 374 行注释：本行执行一个具体步骤，请结合前后文理解它在当前算法中的位置和作用。 */
ConcatSString(&concat_result, &left, &right);
/* 第 375 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&concat_result);
/* 第 376 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("compare left vs right: %d\n", StrCompareSString(&left, &right));
/* 第 377 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("main length: %d\n", StrLengthSString(&main_str));
/* 第 378 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("pattern empty: %s\n", StrEmptySString(&pattern) ? "true" : "false");
/* 第 379 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 380 行注释：本行调用朴素匹配算法，用最直接的方式寻找模式串位置。 */
position_bf = IndexBF(&main_str, &pattern);
/* 第 381 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("BF first match position: %d\n", position_bf);
/* 第 382 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 383 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (GetNextArray(&pattern, next)) {
/* 第 384 行注释：本行打印 next 或 nextval 数组，便于核对 KMP 预处理结果。 */
PrintIntArray1Based(next, pattern.length, "next");
/* 第 385 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 386 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (GetNextValArray(&pattern, nextval)) {
/* 第 387 行注释：本行打印 next 或 nextval 数组，便于核对 KMP 预处理结果。 */
PrintIntArray1Based(nextval, pattern.length, "nextval");
/* 第 388 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 389 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 390 行注释：本行调用 KMP 匹配算法，用 next 数组辅助完成高效匹配。 */
position_kmp = IndexKMP(&main_str, &pattern, next);
/* 第 391 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("KMP first match position: %d\n", position_kmp);
/* 第 392 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 393 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&main_str, "aabaabaabaac");
/* 第 394 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&pattern, "aabaac");
/* 第 395 行注释：本行调用函数求 next 数组，为后续 KMP 匹配提供跳转依据。 */
GetNextArray(&pattern, next);
/* 第 396 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&main_str);
/* 第 397 行注释：本行打印顺序串，方便我们同时观察串值和串长。 */
PrintSString(&pattern);
/* 第 398 行注释：本行打印 next 或 nextval 数组，便于核对 KMP 预处理结果。 */
PrintIntArray1Based(next, pattern.length, "next");
/* 第 399 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("KMP first match position: %d\n", IndexKMP(&main_str, &pattern, next));
/* 第 400 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 401 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&main_str, "aaaaa");
/* 第 402 行注释：本行给顺序串赋值，把普通 C 字符串装进教材风格的串结构。 */
StrAssignSString(&pattern, "aa");
/* 第 403 行注释：本行调用函数求 next 数组，为后续 KMP 匹配提供跳转依据。 */
GetNextArray(&pattern, next);
/* 第 404 行注释：本行统计不重叠匹配次数，便于和允许重叠的结果作对照。 */
match_count = CountPatternMatchesNonOverlapping(&main_str, &pattern, next);
/* 第 405 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("non-overlapping match count in \"aaaaa\" for \"aa\": %d\n", match_count);
/* 第 406 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("overlapping match count in \"aaaaa\" for \"aa\": %d\n",
/* 第 407 行注释：本行统计允许重叠的匹配次数，帮助理解“起始位置个数”和“完整趟数”的差别。 */
CountPatternMatchesOverlappingBF(&main_str, &pattern));
/* 第 408 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 409 行注释：本行开始条件判断，程序会根据条件是否成立选择不同执行路径。 */
if (StrAssignHString(&heap_str, "dynamic string example")) {
/* 第 410 行注释：本行把当前结果打印出来，便于验证函数行为是否符合预期。 */
printf("heap string: \"%s\" length=%d\n", heap_str.ch, heap_str.length);
/* 第 411 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
/* 第 412 行注释：本行销毁堆分配串，主动释放它占用的堆内存。 */
DestroyHString(&heap_str);
/* 第 413 行注释：本行为空行，用来分隔逻辑块，阅读时可以把它当作一处停顿。 */
/* 第 414 行注释：本行返回 0，通常表示未找到、失败，或主函数正常结束。 */
return 0;
/* 第 415 行注释：本行结束当前代码块，说明这一层逻辑已经收束完成。 */
}
继续阅读