📖 第 9.1 章：字符串基础

9.1.0 从一道题出发

题目（改编自 USACO Bronze 风格）

奶牛贝西学会了打字，但它有个坏习惯：按住某个键不放，导致输出里出现成串的重复字符。给定它输出的字符串 s，判断它本来想打的「干净字符串」有多少种可能。

例如 s = "aabb"：可能想打的是 ab、aab、abb、aabb……

输入：一个仅含小写字母的字符串 s（1 ≤ |s| ≤ 10⁵） 输出：在「每个字符最多重复连续按 k 次」规则下……

这道题本身不难——它真正考察的是你对子串、连续段这些基本概念的熟练程度，以及对 string 各种操作的灵活运用。在学 KMP、Trie 这些「高级货」之前，先把地基打牢：字符串到底怎么表示、怎么读入、怎么切、怎么比、怎么拼。

9.1.1 基本概念

以下设字符串 S，下标从 0 开始，长度记为 |S|。例如 S = "abcabcd"：

⚠️ 三个最容易混的点：

1. 子串 ⊆ 子序列。子串必须连续，子序列可以跳着取。"acd" 是 "abcabcd" 的子序列但不是子串。
2. 字典序中「短的前缀更小」："ab" < "aba"。比较时把「提前结束」当成「遇到一个比任何字符都小的空字符」。
3. 空串 ε：长度为 0 的串，是任何串的前缀和后缀。写边界条件时别漏掉它。

9.1.2 读入字符串：竞赛中的三大坑

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n;
    // 坑 1：cin >> n 后缓冲区里残留一个换行符，
    // 直接 getline 会读到一个空串！
    cin.ignore();          // 吃掉残留换行
    getline(cin, s);       // 读一整行（可以带空格）

    string word;
    cin >> word;           // 坑 2：cin >> 按空白切分，读不了空格
    cout << word << "\n";

    // 坑 3：想读「恰好 k 个字符」时，用循环 + 单字符读入更稳
    string t;
    for (int i = 0; i < 3; i++) {
        char c = cin.get(); // 逐字符读，包括空格和换行
        t += c;
    }
    cout << t << "\n";
}

牢记：cin >> int 之后想 getline，中间必须 cin.ignore()。这是 Bronze/Silver 字符串题的头号丢分点。

竞赛中最常用的是 cin >> s（不含空格的 token）和 getline(cin, s)（整行）两种，按题意选。

9.1.3 string 常用操作速成

std::string 是竞赛里唯一的字符串选择（C 风格 char[] 只有在 scanf("%s") 混读时偶尔遇到）。掌握下面这些就够用：

string s = "hello world";

// —— 长度与访问 ——
s.size();          // 长度 11（返回无符号类型，见下方陷阱）
s.length();        // 同上
s[0];              // 'h'，下标访问 O(1)
s.back();          // 'd'，最后一个字符
s.front();         // 'h'，第一个字符

// —— 拼接与赋值 ——
string a = "abc", b = "de";
string c = a + b;  // "abcde"，O(|a|+|b|)
a += "xy";         // 尾部追加，均摊 O(1)

// —— 比较：直接用运算符，按字典序 ——
// "ab" < "aba" < "b"
if (a < b) { /* ... */ }

// —— 查找：find 返回首位置，找不到返回 string::npos ——
s.find("world");       // 6
s.find('o');           // 4（也能查单个字符）
s.rfind('o');          // 7（从后往前找）
if (s.find("xyz") == string::npos) { /* 没找到 */ }

// —— 截取：substr(起点, 长度)，注意第二个参数是长度不是终点 ——
s.substr(6);       // "world"
s.substr(0, 5);    // "hello"

// —— 插入 / 删除 / 替换 ——
s.insert(5, "!");      // "hello! world"
s.erase(5, 1);         // 删掉位置 5 起的 1 个字符
s.replace(0, 5, "Hi"); // "Hi world"

// —— 排序与反转 ——
sort(s.begin(), s.end());      // 把字符排序（常用于「重排后判断」类题）
reverse(s.begin(), s.end());   // 反转（判回文的朴素写法）

// —— 与数字互转 ——
int x = stoi("42");            // string → int（还有 stoll 转 long long）
string t = to_string(12345);   // int → string

⚠️ 常见错误

9.1.4 C 风格字符串与 <cstring>

竞赛代码里偶尔还是会碰到 C 风格的 char 数组（读入函数、老模板、题解代码里都常见）。认识它们，能看懂、能互转就够了——自己写新代码时优先用 string。

char 数组与 C 函数速查

#include <cstring>   // strlen / strcmp / strcpy / strstr ...

char s[105];
scanf("%s", s);              // 读一个 token（不含空格），自动补 '\0'
// scanf 读 char 数组不加 & —— s 本身就是地址！

strlen(s);                   // 长度：从头数到 '\0'，O(N)！
strcmp(s, "abc");            // 字典序比较：<0 / 0 / >0
                             // ⚠️ 返回值不保证只是 -1/0/1，只能看符号！
strcpy(s, "hello");          // 复制
strcat(s, "world");          // 拼接到末尾
strstr(s, "lo");             // 查子串，返回指针；没找到返回 NULL
strchr(s, 'l');              // 查字符首次出现
strrchr(s, 'l');             // 查字符最后一次出现

三个要点：

1. '\0' 结尾：C 字符串靠一个隐藏的空字符标记结束。char s[105] 最多存 104 个可见字符——数组开小一位是经典越界原因。
2. strlen 是 O(N)：写在循环条件里（for (int i = 0; i < strlen(s); i++)）会让整个循环变 O(N²)。先存进变量：int n = strlen(s);。
3. strcmp 只看符号：判断相等写 strcmp(a, b) == 0，别写 == 1 或 == -1——标准只保证符号。

string 与 char 数组互转

string a = "hello";
const char* p = a.c_str();   // string → char*（scanf("%s", buf) 等场景）
                             // ⚠️ a 后续被修改后 p 失效，别长期持有
string b(p);                 // char* → string
string c = p;                // 同上

// 读一整行到 char 数组（老写法，了解即可）：
char line[1005];
cin.getline(line, 1005);     // 或 fgets(line, 1005, stdin)

sprintf / sscanf：字符串当「格式化插座」用

这一对函数在字符串题里非常好用——把变量拼进字符串、从字符串里按格式抠出变量：

#include <cstdio>
char buf[1005];

// sprintf：把格式化的内容写进字符串
int id = 3;
sprintf(buf, "cow_%d", id);          // buf = "cow_3"
sprintf(buf, "%d-%d", 5, 12);        // buf = "5-12"
double x = 3.14159;
sprintf(buf, "%.2f", x);             // buf = "3.14" —— 浮点保留位数最方便的写法

// sscanf：从字符串里按格式解析变量
int a, b;
sscanf("5 12", "%d %d", &a, &b);     // a=5, b=12
int hh, mm;
sscanf("07:45", "%d:%d", &hh, &mm);  // hh=7, mm=45 —— 带分隔符的解析神器
char name[30];
sscanf("Bessie 10", "%s %d", name, &a); // name="Bessie", a=10

典型场景：

• 日期/时间解析：sscanf("2026-09-16", "%d-%d-%d", &y, &m, &d) 一行搞定，比手写逐字符解析稳得多。
• 构造输出名 / 中间串：把数字嵌进字符串时用 sprintf（或 to_string 拼接，两者都行）。
• 浮点格式化输出：printf("%.3f", x) 与 sprintf(buf, "%.3f", x) 共享同一套格式语法。

💡 选型建议：新代码一律 string + cin/cout；只在①读老模板②格式化解析（sscanf）③scanf 提速混读时碰 char[]。sscanf/sprintf 即使在 string 时代也值得留在工具箱里。

9.1.5 判断回文与统计字符

两个最基础但出镜率极高的模板：

// 判断回文：双指针从两端向中间夹
bool isPalindrome(const string& s) {
    for (int i = 0, j = (int)s.size() - 1; i < j; i++, j--)
        if (s[i] != s[j]) return false;
    return true;
}

// 统计每个字符出现次数：桶计数，O(N)
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
// cnt[0] 是 'a' 的次数……之后可判断「能否重排成回文」：
// 回文条件 = 出现奇数次的字符数 ≤ 1

字符 ↔ 下标转换是字符串题的基本功：c - 'a' 把小写字母映射到 0~25，c - '0' 把数字字符转成数值，反过来 'a' + i 转回字符。

9.1.6 实战例题：重复字符清理

题目：给定字符串 s，把其中连续相同的字符压缩成「字符 + 次数」（如 "aaabb" → a3b2），输出压缩后的串；若压缩后不比原串短，输出原串。

这是「连续段」（也叫 run）思想的入门题——统计连续相同字符的个数这个动作会在无数字符串题中反复出现（第 9.4 章 Manacher、构造题、枚举题里都有它）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;

    string comp = "";
    int n = s.size();
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;   // 找到连续段的终点
        comp += s[i];
        comp += to_string(j - i);            // 段长
        i = j;                               // 跳到下一个连续段
    }

    if (comp.size() < s.size()) cout << comp << "\n";
    else cout << s << "\n";
    return 0;
}

手算样例：s = "aaabb" → 段为 a×3, b×2 → comp = "a3b2"（长度 4 < 5）→ 输出 a3b2。 s = "abc" → a1b1c1（长度 6 > 3）→ 输出 abc。

注意这个「i 直接跳到段尾 j」的写法：内层 while 把每个字符恰好看一次，整体 O(N)——比「每处理一个字符就把整个后缀重新扫一遍」的朴素写法快得多。

9.1.7 综合练习

🟢 9.1-E1（回文判断） 给定字符串 s（|s| ≤ 10⁵），判断去掉所有非字母字符并转为小写后，剩下的串是否为回文。 样例："A man, a plan!" → 字母序列 "amanaplan"，非回文，输出 NO。

🟢 9.1-E2（最小字典序） 输入 N 个字符串（N ≤ 100，每个长度 ≤ 100），输出其中字典序最小的串。 提示：直接维护 string best; if (s < best) best = s;，C++ 的 < 就是字典序。

🟡 9.1-E3（首尾配对） 给定 N 个字符串，统计有多少对 (i, j)（i < j）满足：把 sᵢ 和 sⱼ 首尾相接（两种顺序都试）后是回文串。N ≤ 1000，串长 ≤ 10。 提示：串长很小，直接拼起来用 9.1.4 的回文判断；也可以只统计各串首尾字符的计数关系。

🟡 9.1-E4（压缩再还原） 先按 9.1.5 的规则压缩字符串，再实现逆操作：给定 a3b2 这样的压缩串，还原出 aaabb。 提示：stoi 解析数字段，注意次数可能是多位数。

🔴 9.1-E5（循环移位匹配） 给定 s 和 t（|s| = |t| ≤ 10⁵），判断 t 是否为 s 的循环移位（即把 s 的某个前缀搬到末尾后恰好等于 t）。 样例：s = "abcde"，t = "deabc" → 是。 提示：(s + s).find(t) != string::npos 一行搞定——想想为什么拼接后 t 必然是它的子串。

本章总结

学完本章，你应该能徒手写出：读入、拼接比较、找子串、判回文、统计连续段。下一章（9.2）我们会看到：当 find 的朴素 O(N·M) 扛不住 10⁵ 规模时，KMP 如何用「失配跳转」把匹配降到线性。

💡 下一章预告：9.1 里所有 find 类操作都是朴素的。第 9.2 章的前缀函数与 KMP 会彻底解决这个问题——而且它定义的「border」概念，会在 Trie、AC 自动机里一路复用。