十、字符串

这是最后一页，5 章 33 道题。

字符串题的特点是：逻辑不难，细节极多。 算法你可能一眼就想到，但空格、换行、大小写、末尾的 \0、scanf 读到哪停下……每一处都能让你 WA 半天。

所以这一页的重点不是「想不出来怎么做」，而是「想到了但写不对」。33 道题，大部分失分都在细节上。

先把最要紧的三件事记住：

1. 字符数组的结尾有一个 \0，它不算内容，但占一个位置
2. scanf("%s") 遇到空格就停，读不了带空格的一整行
3. 字符串不能直接用 == 比较，要用 strcmp

31. 字符与字符串基础

31.1 char 数组与 string

C++ 有两种字符串，初学阶段建议先用 char 数组：

char s[105];                  // 能装 104 个字符 + 结尾的 '\0'
scanf("%s", s);               // 注意：不加 &
printf("%s\n", s);

%s 读入时，s 前面不加 &——因为数组名本身就是地址。加了反而错。

另一种是 C++ 的 string 类型：

string s;
cin >> s;                     // string 要用 cin 读
cout << s << endl;

string 更方便（能直接 =、+、==），但它不能用 scanf 读。既然全站用 scanf，那就用 char 数组，一以贯之。

一个字符数组装 n 个字符，至少要开 n+1 个位置，因为末尾要放一个 \0（字符串结束标志）。\0 的码值是 0，不是字符 '0'。

char s[6] = "hello";
// s[0]='h' s[1]='e' s[2]='l' s[3]='l' s[4]='o' s[5]='\0'

char s[5];
scanf("%s", s);      // 输入 "hello" 是 5 个字符，但需要 6 个位置

31.2 读一整行

scanf("%s", s) 遇到空格或换行就停。所以输入 hello world，它只读到 hello。

要读带空格的一整行，用 fgets：

char s[105];
fgets(s, sizeof(s), stdin);

三个参数：装到哪、最多读多少、从哪读（stdin 是标准输入）。

fgets 会把行末的换行符也读进来。 所以读完之后通常要去掉：

int len = strlen(s);
if (len > 0 && s[len-1] == '\n') s[len-1] = '\0';

这一步不做的话，你输出的内容末尾会多一个空行，或者字符串比较时永远不相等。

另一种写法是 scanf("%[^\n]", s)，意思是「读到换行为止」：

scanf(" %[^\n]", s);     // 前面那个空格很重要，用来跳过上一行留下的换行

%[^\n] 是「字符集合」的写法，^\n 表示「除了换行以外的所有字符」。

int n;
scanf("%d", &n);         // 读完数字，回车还留在缓冲区
fgets(s, sizeof(s), stdin);   // 读到一个空行！

31.3 遍历与修改

遍历字符串，就是遍历到 \0 为止：

for (int i = 0; s[i] != '\0'; i++) {
    // 处理 s[i]
}

或者先求长度：

int len = strlen(s);        // 需要 #include <cstring>，bits 里有
for (int i = 0; i < len; i++) {
    // 处理 s[i]
}

两种写法等价。第一种少算一次长度，第二种可以在循环里用 len。

strlen 的复杂度是 O(n)——它要从头数到 \0。所以不要在循环条件里反复调用 strlen(s)：

for (int i = 0; i < strlen(s); i++)    // 错：每次都重算一遍，变成 O(n²)

正确做法是先存下来：int len = strlen(s);。

31.4 大小写转换

char c = 'a';
char upper = c - 'a' + 'A';    // 'A'
char lower = 'A' - 'A' + 'a';  // 'a'

因为大小写字母各自的码值是连续的，所以「减掉小写起点，加上大写起点」就能转换。

也有现成的函数：

toupper(c);      // 转大写，如果是小写的话
tolower(c);      // 转小写

toupper 对非字母字符原样返回，所以不用先判断。

32. 遍历、统计与判定

32.1 用遍历做判定

「这个字符串是不是合法的 C 标识符」「两个字符串有百分之多少相同」——本质都是遍历一遍，逐字符检查。

bool ok = true;
for (int i = 0; s[i]; i++) {
    if (!(isalnum(s[i]) || s[i] == '_')) {    // 不是字母数字下划线
        ok = false;
        break;
    }
}

isalnum(c) 判断是不是字母或数字，isalpha(c) 判断字母，isdigit(c) 判断数字。都在 <cctype> 里，bits 已包含。

注意 C 标识符不能以数字开头——这个条件要单独判断 s[0]。

32.2 配对与镜像

「碱基配对」这类题：A 配 T、C 配 G。写法就是逐字符判断后输出对应的字符。

for (int i = 0; s[i]; i++) {
    if (s[i] == 'A') printf("T");
    else if (s[i] == 'T') printf("A");
    else if (s[i] == 'C') printf("G");
    else if (s[i] == 'G') printf("C");
}

如果配对规则很多，用两个数组做映射表更清爽：

char from[] = "ATCG";
char to[]   = "TAGC";
for (int i = 0; s[i]; i++) {
    for (int j = 0; from[j]; j++) {
        if (s[i] == from[j]) { printf("%c", to[j]); break; }
    }
}

32.3 回文判断

从头尾两头往中间比：

int len = strlen(s);
bool ok = true;
for (int i = 0; i < len / 2; i++) {
    if (s[i] != s[len - 1 - i]) {
        ok = false;
        break;
    }
}

len / 2 是重点——只需要比一半，全部比完是浪费。奇偶都不用特殊处理：len = 5 时 len/2 = 2，比 s[0] 和 s[4]、s[1] 和 s[3]，中间那个 s[2] 自己和自己相等，不用比。

32.4 用计数数组统计字符

字符的码值范围是 0~127，可以开一个 128 大小的数组当桶：

int cnt[128] = {0};
for (int i = 0; s[i]; i++) cnt[s[i]]++;
// cnt['a'] 就是 'a' 出现的次数

这是桶的思想在字符上的应用——用字符的码值当下标，第 23 章学过。

33. 字符映射与加解密

这一章的所有题，本质都是把字符按某个规则换成另一个字符。规则不同，套路一样。

33.1 偏移：凯撒密码

每个字母往后移 k 位，超出 z 就回到 a。

char shift(char c, int k) {
    if (c >= 'a' && c <= 'z') return (c - 'a' + k) % 26 + 'a';
    if (c >= 'A' && c <= 'Z') return (c - 'A' + k) % 26 + 'A';
    return c;                    // 非字母原样返回
}

第 6 章讲过这个套路：减掉起点 → 做运算 → 加回起点。% 26 负责回绕。

注意非字母字符要原样保留（空格、标点、数字）。很多题就靠这一点设坑。

33.2 大小写混合的规则

有些题要求「大写转小写，小写转大写，其他不变」，还有些要求「只处理字母，非字母跳过」。

if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';
else if (c >= 'a' && c <= 'z') c = c - 'a' + 'A';

用 if / else if 而不是两个独立的 if——先转成小写再判断是不是小写，会转两次，结果又变回大写。第 9 章讲的「独立 if 和 else if 的区别」，在这里会真实咬人。

33.3 建立映射表

「潜伏者」这类题，给一张密码表和对应的明文，要你推出整个映射关系。

这种题的通用做法是开两张表：

char enc[26], dec[26];    // enc[明文] = 密文, dec[密文] = 明文
bool used[26] = {false};

然后：

1. 遍历样例，把每一对「明文-密文」存进两张表
2. 检查有没有矛盾（同一个明文字母对应了两个不同密文）
3. 检查 26 个字母是不是都被映射了

这类题难在逻辑，不在字符串操作。 先把「什么情况下算冲突」「什么情况下算不完整」想清楚，再写代码。

34. 比较、子串与循环移位

34.1 字符串比较

不能用 ==——s1 == s2 比较的是两个数组的地址，永远不相等。

要用 strcmp：

if (strcmp(s1, s2) == 0) printf("same\n");

strcmp 返回：

• 0：两个字符串完全相同
• 负数：s1 字典序小于 s2
• 正数：s1 字典序大于 s2

记住只判断 == 0 和 != 0 就够了，具体返回多少不用管。

忽略大小写的比较，先把两边都转成小写再比：

for (int i = 0; s1[i]; i++) s1[i] = tolower(s1[i]);
for (int i = 0; s2[i]; i++) s2[i] = tolower(s2[i]);
if (strcmp(s1, s2) == 0) { ... }

34.2 查找子串

char *p = strstr(s, t);      // 在 s 里找 t
if (p != NULL) {
    printf("%d\n", (int)(p - s));   // 找到的位置（从 0 开始）
}

strstr 返回一个指针，指向第一次出现的位置。p - s 就是偏移量。

找不到时返回 NULL（空指针）。

不想用指针的话，手写两层循环也行：

bool found = false;
for (int i = 0; s[i]; i++) {
    bool ok = true;
    for (int j = 0; t[j]; j++) {
        if (s[i+j] != t[j]) { ok = false; break; }
    }
    if (ok) { found = true; break; }
}

34.3 循环移位

「判断 s2 是不是 s1 循环移位得到的」有个巧办法：把 s1 接上自己，看 s2 是不是它的子串。

char t[205];
strcpy(t, s);
strcat(t, s);          // t = s + s
if (strstr(t, s2) != NULL) { /* 是循环移位 */ }

比如 s = abcd，接上自己是 abcdabcd，里面包含 bcda、cdab、dabc——正好是所有循环移位。

strcpy 是复制，strcat 是拼接。两个都要保证目标数组够大（这里是 205，因为要装两倍长度）。

34.4 多分支列举

35. 单词处理与综合

这一章的题都是「处理一句话」——切词、替换、统计。

35.1 按空格切词

最朴素的做法：

for (int i = 0; s[i]; i++) {
    if (s[i] != ' ') {
        word[wlen++] = s[i];       // 累积到缓冲区
    } else if (wlen > 0) {
        word[wlen] = '\0';         // 一个词结束
        处理(word);
        wlen = 0;                  // 清空
    }
}
if (wlen > 0) { word[wlen] = '\0'; 处理(word); }   // 处理最后一个词

注意两件事：

1. 连续多个空格要跳过（wlen > 0 那个判断）
2. 循环结束后最后一个词要单独处理（因为它后面没有空格）

第 2 点是最高频的错——最后一个词被吃掉。

另一种更简单的方式：用 scanf("%s") 连续读，它自动跳过所有空格。

char word[105];
while (scanf("%s", word) == 1) {
    // 处理 word
}

scanf 返回成功读入的项数，读到文件末尾返回 EOF（-1）。这个写法在处理「不知道有多少个词」时特别好用，而且不用管多个空格的问题。

35.2 单词替换与倒排

替换单词的坑在于：不能直接找子串替换。

比如把 he 替换成 she，字符串是 the hero——直接找 he 会命中 the 里的 he，变成 tshe shero。

正确做法是先切词，按词判断：

while (scanf("%s", word) == 1) {
    if (strcmp(word, target) == 0) printf("%s ", replacement);
    else printf("%s ", word);
}

倒排更简单：把词读进一个数组，倒着输出。

char w[1005][105];
int n = 0;
while (scanf("%s", w[n]) == 1) n++;
for (int i = n - 1; i >= 0; i--) printf("%s ", w[i]);

35.3 行程长度编码

把连续重复的字符压缩成「字符 + 次数」：aaabbc → a3b2c1。

int i = 0;
while (s[i]) {
    int j = i;
    while (s[j] == s[i]) j++;      // 找到相同字符的结尾
    printf("%c%d", s[i], j - i);   // 字符 + 个数
    i = j;                          // 从下一个字符继续
}

这个「两个指针，一个标记起点、一个往后探」的写法，在字符串题里会反复出现。

35.4 校验与格式判定

35.5 综合

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 可以先看：string —— 只看开头「string 是什么」。后面 substr、find 那些函数第 34 章才用得上
• 学完这一页再看：字符串基础 —— 字符串的存储方式。看完能解释 s[i] 为什么能取到第 i 个字符
• 现在跳过：字符串哈希 —— 比较字符串的竞赛级做法。你现在用 strcmp 就够了，别碰