企业官网建设流程全解析

在实际算法竞赛训练中，字符串处理是区分选手基本功与进阶能力的关键分水岭。无论是处理用户输入、解析复杂数据，还是实现高效的文本匹配与模式查找，字符串相关的算法都构成了 ACM 竞赛和日常编程的核心。很多初学者在掌握了基本语法后，面对诸如“大整数比较”、“子串查找”、“模式匹配”等问题时，往往感到无从下手，或者只能写出时间复杂度无法接受的低效代码。本文将以西安交通大学 ACM 算法竞赛小学期课程第九天的内容为脉络，系统梳理字符串处理的核心算法与实战技巧，重点剖析哈希（Hash）与 KMP（Knuth-Morris-Pratt）这两大基石算法。我们将从概念入手，通过 C++ 实现，并结合典型竞赛题目，让你不仅理解算法原理，更能掌握在 ACM 模式下快速、准确实现并调试代码的能力。学完后，你将能够独立解决涉及字符串匹配、循环节、前后缀分析等常见竞赛题型。

1. 理解字符串处理的核心挑战与竞赛输入输出

在算法竞赛中，字符串问题之所以具有挑战性，主要源于其两个特性：一是长度可能极大（如超过 10^5），使得 O(n²) 的朴素算法必然超时；二是需要处理各种边界条件，如空串、特殊字符、编码问题等。此外，ACM 模式下的输入输出处理本身就是一个需要熟练掌握的技能。

1.1 ACM 模式下的 C++ 字符串输入输出

与 LeetCode 等平台只需完成函数不同，ACM 竞赛要求处理完整的标准输入输出。对于字符串，常见的输入方式有：

1. 对于不含空格的字符串：可以直接使用cin >> str或scanf(“%s”, char_array)。
2. 对于包含空格的整行字符串：必须使用getline(cin, str)。但需要注意，getline会读取cin或scanf后残留的换行符，导致读取到空行。

#include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; // 读取一个整数 cin.ignore(); // 忽略掉整数后面的换行符，这是关键！ string s; getline(cin, s); // 此时才能正确读取后续的整行字符串 cout << “读取的字符串是：” << s << endl; return 0; }

3. 对于已知长度的多行字符串：有时题目会先给出字符串长度n，然后下一行给出一个长度为n的字符串。此时可以直接cin >> str，因为字符串本身不含空格。

常见坑点：混合使用cin和getline时忘记清空缓冲区，导致getline读取到空字符串。解决方案是在cin后使用cin.ignore()。

1.2 C++string与 C 风格字符数组的选择

在竞赛中，std::string是更推荐的选择，因为它更安全、功能更丰富（如find,substr）。但在对性能有极致要求，或者需要与某些 C 库函数交互时，可能会用到字符数组。

// 使用 std::string string s1 = “Hello”; s1 += “ World”; // 拼接方便 int len1 = s1.length(); // 使用 C 风格字符数组 char s2[100] = “Hello”; strcat(s2, “ World”); // 需确保数组空间足够 int len2 = strlen(s2);

注意：在竞赛中，除非特别必要，优先使用std::string。使用字符数组时，务必警惕缓冲区溢出的风险。

2. 字符串哈希：快速比较与子串匹配的利器

当需要频繁比较两个字符串是否相等，或者比较一个字符串的多个子串时，逐字符比较的 O(n) 复杂度在嵌套循环下会变得不可接受。字符串哈希的核心思想是将一个字符串映射为一个整数（哈希值），使得比较两个字符串转化为比较两个整数，从而实现 O(1) 的比较。

2.1 哈希函数的设计与冲突

一个理想的字符串哈希函数需要尽可能减少“冲突”（即不同字符串计算出相同哈希值）。常见的哈希方法是“多项式滚动哈希”。

假设字符串S = s[0]s[1]…s[n-1]，我们将其视为一个P进制的数。 定义哈希函数：hash(S) = (s[0] * P^(n-1) + s[1] * P^(n-2) + … + s[n-1] * P^0) mod M

其中：

• P是一个质数基数，通常取 131 或 13331。
• M是一个大质数模数，用于将哈希值控制在一定范围内，通常取 2^64（即利用unsigned long long的自然溢出）或 1e9+7。

为什么选择质数？质数可以使得哈希分布更均匀，减少冲突。

2.2 前缀哈希与子串哈希计算

单次计算整个字符串的哈希值意义不大。强大的地方在于，我们可以预处理出字符串所有前缀的哈希值，从而在 O(1) 时间内计算出任意子串的哈希值。

定义：

• h[i]表示字符串S前i个字符的哈希值（h[0] = 0）。
• p[i]表示P^i。

预处理：h[i] = (h[i-1] * P + S[i-1]) % Mp[i] = (p[i-1] * P) % M

那么，子串S[l…r]（下标从 1 开始，左闭右闭）的哈希值为：hash(l, r) = (h[r] - h[l-1] * p[r-l+1] % M + M) % M

这个公式的本质是：将高位对齐后相减。h[l-1] * p[r-l+1]相当于把前缀[1…l-1]的哈希值左移到与[1…r]对齐的位置。

#include <iostream> #include <string> #include <vector> using namespace std; typedef unsigned long long ULL; const int P = 131; // 质数基数 int main() { string s = “ababc”; int n = s.length(); vector<ULL> h(n + 1, 0); // 哈希前缀数组 vector<ULL> p(n + 1, 0); // 幂次数组 p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * P + s[i - 1]; // 利用 unsigned long long 自然溢出取模 p[i] = p[i - 1] * P; } // 计算子串 s[2…4] (”abc”) 的哈希值，下标从1开始 int l = 2, r = 4; ULL hash_lr = h[r] - h[l - 1] * p[r - l + 1]; cout << “子串 \”abc\” 的哈希值（示例）: ” << hash_lr << endl; // 比较两个子串是否相等 // 假设比较 s[1…2] (“ab”) 和 s[3…4] (“bc”) int l1 = 1, r1 = 2; int l2 = 3, r2 = 4; ULL hash1 = h[r1] - h[l1 - 1] * p[r1 - l1 + 1]; ULL hash2 = h[r2] - h[l2 - 1] * p[r2 - l2 + 1]; if (hash1 == hash2) { cout << “子串相等” << endl; } else { cout << “子串不相等” << endl; } return 0; }

2.3 哈希的典型应用场景

1. 字符串快速比较：在循环中需要比较大量子串时。
2. 判断字符串循环节：字符串S由某个子串重复构成，其长度len需能被字符串长度n整除，且满足hash(1, n-len) == hash(len+1, n)。
3. 配合二分查找解决最长回文子串、最长公共子串等问题。

常见坑点：

• 哈希冲突：单哈希（一个P和一个M）在数据量极大时仍有冲突风险。竞赛中应对极端数据可采用双哈希（使用两组P和M），只有当两个哈希值都相等时才判定字符串相等。
• 取模运算：如果使用% M，减法后可能得到负数，需要(x % M + M) % M来修正。
• 自然溢出：使用unsigned long long自然溢出相当于对2^64取模，代码简洁且效率高，在大多数竞赛题目中足够安全。

3. KMP 算法：高效的单模式字符串匹配

字符串匹配的经典问题是：给定一个文本串T和一个模式串P，找出P在T中所有出现的位置。朴素的暴力匹配算法时间复杂度为 O(n*m)。KMP 算法通过一个巧妙的next数组，将时间复杂度优化到 O(n+m)。

3.1 核心思想：利用已匹配的信息

KMP 算法的精髓在于，当某次匹配失败时，模式串P不是简单地后移一位从头开始匹配，而是利用之前已经匹配成功的信息，跳转到某个位置继续匹配。这个“跳转位置”由next数组决定。

next[i]的定义是：模式串P的前缀P[0…i]中，最长的、相等的真前缀与真后缀的长度。

• 真前缀：不包括字符串本身的前缀。
• 真后缀：不包括字符串本身的后缀。

例如，对于模式串P = “ababc”：

• next[0] = 0（单个字符，没有真前缀和真后缀）
• next[1] = 0（”ab”，真前缀 “a”，真后缀 “b”，不相等）
• next[2] = 1（”aba”，真前缀有 “a”, “ab”，真后缀有 “ba”, “a”，相等的只有 “a”，长度为1）
• next[3] = 2（”abab”，相等的真前缀和真后缀有 “ab”，长度为2）
• next[4] = 0（”ababc”，没有相等的真前缀和真后缀）

3.2 next 数组的计算

计算next数组的过程可以看作是模式串P与自身进行匹配。

vector<int> getNext(const string& p) { int m = p.length(); vector<int> next(m, 0); // next[0] 一定是 0 for (int i = 1, j = 0; i < m; i++) { // 当 j > 0 且 p[i] != p[j] 时，回退 j while (j > 0 && p[i] != p[j]) { j = next[j - 1]; } // 如果 p[i] == p[j]，则 j 前进一步 if (p[i] == p[j]) { j++; } // 记录 next[i] next[i] = j; } return next; }

关键解释：变量i指向当前待计算next值的位置（后缀末尾），j指向前缀末尾（同时也是已匹配的长度）。while循环中的j = next[j - 1]是 KMP 最精妙的部分，它意味着当失配时，j不是退回 0，而是退回到next[j-1]所指示的位置，继续尝试匹配。

3.3 利用 next 数组进行匹配

有了next数组，匹配过程就非常清晰了。

vector<int> kmpSearch(const string& t, const string& p) { vector<int> next = getNext(p); vector<int> positions; // 存储所有匹配的起始位置 int n = t.length(), m = p.length(); for (int i = 0, j = 0; i < n; i++) { // 失配时，根据 next 数组回退 j while (j > 0 && t[i] != p[j]) { j = next[j - 1]; } // 当前字符匹配成功，j 前进 if (t[i] == p[j]) { j++; } // 完全匹配了一个模式串 if (j == m) { positions.push_back(i - m + 1); // 记录起始下标 j = next[j - 1]; // 继续寻找下一个匹配 } } return positions; } int main() { string text = “abababcabab”; string pattern = “abab”; vector<int> res = kmpSearch(text, pattern); cout << “模式串 \”” << pattern << “\” 在文本串中出现的位置：”; for (int pos : res) cout << pos << “ “; // 输出 0 2 7 cout << endl; return 0; }

3.4 KMP 算法的典型应用

1. 单模式匹配：最基本的应用。
2. 求字符串循环节：若字符串长度len能被(len - next[len-1])整除，则len / (len - next[len-1])就是循环节出现的次数。例如“ababab”的next[5]=4，6/(6-4)=3，循环节“ab”出现 3 次。
3. 前后缀问题：next数组本身记录了每个前缀的最长公共前后缀长度。

常见坑点：

• 下标从 0 开始与从 1 开始：上述代码是下标从 0 开始的 C++ 风格。有些资料或题目下标从 1 开始，next[0]可能被设为 -1 或 0，代码写法略有不同，但核心思想一致。务必理解本质，而不是死记模板。
• next 数组的命名：有些实现中这个数组叫fail或pi。
• 匹配完成后的回退：找到一次匹配后，执行j = next[j - 1]是为了继续寻找所有可能的重叠匹配（如“aaaa”中找“aa”）。

4. 综合实战：大整数比较与字符串转换问题

回到输入材料中提到的实际问题：“给两个大整数，用字符串表示，比如 ‘2154365543’， ‘32656442’，都可能超过1万位”。这种大整数无法用int或long long存储，必须用字符串处理。

4.1 大整数比较

比较两个大整数字符串a和b：

1. 先比较长度，长度长的数值更大。
2. 若长度相等，则从最高位（字符串开头）开始逐字符比较。

int compareBigInt(const string& a, const string& b) { if (a.length() != b.length()) { return a.length() > b.length() ? 1 : -1; } // 长度相等，逐位比较 for (int i = 0; i < a.length(); i++) { if (a[i] != b[i]) { return a[i] > b[i] ? 1 : -1; } } return 0; // 相等 }

4.2 大整数加法（字符串实现）

模拟竖式加法，从最低位（字符串末尾）开始相加，处理进位。

string addBigInt(const string& num1, const string& num2) { string result; int i = num1.length() - 1, j = num2.length() - 1; int carry = 0; // 进位 while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += num1[i--] - ‘0’; if (j >= 0) sum += num2[j--] - ‘0’; carry = sum / 10; result.push_back(sum % 10 + ‘0’); } reverse(result.begin(), result.end()); // 结果需要反转 return result; }

4.3 字符串与数值类型的转换问题

在开发中，常遇到“将字符串转换为 uniqueidentifier 时失败”或“录入数据库字符串变成??”等问题。这通常与字符编码有关。

• 编码问题：确保程序、数据库、终端的字符编码一致（如 UTF-8）。在 C++ 中读取文件或网络数据时，明确指定编码。
• 非法字符：在将字符串用于 SQL 语句或 XML 前，需要进行适当的转义或过滤，防止注入攻击或解析错误。例如，XML 中的<,>,&等字符需要转换为实体<,>,&。

5. 常见问题排查与最佳实践

字符串问题调试起来往往令人头疼，错误现象可能和根源相距甚远。

5.1 常见问题排查表

5.2 竞赛中的字符串最佳实践

1. 输入读取鲁棒性：对于不确定格式的输入，可以先用getline读取一整行，再用stringstream进行分割解析。
2. 空间预先分配：对于std::string，如果已知最终大小，可以使用reserve()预分配空间，减少多次重新分配的开销。
3. 避免不必要的拷贝：传递字符串时，尽量使用const string&引用，避免值拷贝。特别是长字符串。
4. 哈希的封装：将哈希的预处理、子串计算封装成一个类或结构体，使主逻辑更清晰。
5. 模板化 KMP：将 KMP 的getNext和search函数写成模板，适用于string和vector<T>等类型。
6. 调试输出：在调试复杂字符串算法时，将关键的中间变量（如next数组、哈希值、循环下标）打印出来，与手工计算的结果对比。

5.3 扩展学习方向

掌握了哈希和 KMP 之后，字符串算法的世界才刚刚打开：

• 扩展 KMP (Z-algorithm)：用于计算每个后缀与整个字符串的最长公共前缀，解决更多前后缀问题。
• 字典树 (Trie)：高效存储和检索字符串集合，用于词频统计、前缀匹配。
• AC 自动机：KMP 在多模式串匹配上的扩展，结合了字典树，用于敏感词过滤等场景。
• 后缀数组与后缀自动机：更高级的数据结构，用于解决复杂的子串、回文、重复串问题，是解决字符串难题的利器。

字符串算法的学习，关键在于理解其思想，并通过大量练习将模板内化。从每次匹配失败后模式串该如何移动（KMP），到如何将子串映射为可比较的数字（哈希），这些思想远比记忆代码更重要。在解决具体问题时，先分析数据规模，判断是否需要 O(n) 或 O(n log n) 的算法，再选择合适的工具，这才是算法竞赛训练希望培养的能力。