第28章 字符串相关算法
搜索知识点 /

第28章 字符串相关算法

GESP 三级定位
等级知识块考查频率
GESP C++ 三级字符串函数：大小写转换、查找、分割、替换⭐⭐⭐

字符串算法用于处理文本的查找、替换、匹配、反转、分割等操作，在文本处理与竞赛中应用极广。本章给出各类操作的核心实现（C / C++），并配图说明子串查找过程。

28.1 字符串查找算法

28.1.1 查找单个字符

C 语言实现（遍历到 \0）：

char_find.c
#include <stdio.h>
int main() {
    char str[] = "hello";
    char c = 'l';
    int pos = -1;                  // -1 代表未找到
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == c) { pos = i; break; }
    }
    printf("字符 '%c' 第一次出现位置：%d\n", c, pos);
    return 0;
}

C++ string 实现（用 find）：

char_find_cpp.cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
    string str = "hello";
    size_t pos = str.find('l');
    if (pos != string::npos) cout << "位置：" << pos << endl;
    else cout << "未找到" << endl;
    return 0;
}

28.1.2 暴力匹配查找子串

主串逐个起点与子串逐位比较，失败则主串后移、子串重置。

substr_find.c
#include <stdio.h>
#include <string.h>
int main() {
    char str[] = "ababcabcd";
    char sub[] = "abc";
    int strLen = strlen(str), subLen = strlen(sub);
    int pos = -1;
    for (int i = 0; i <= strLen - subLen; i++) {
        int j;
        for (j = 0; j < subLen; j++)
            if (str[i + j] != sub[j]) break;
        if (j == subLen) { pos = i; break; }
    }
    printf("子串首次起始下标：%d\n", pos);   // 2
    return 0;
}

子串暴力匹配滑动过程

28.2 字符串替换算法

把指定旧子串全部替换为新子串（C++ string）：

replace_all.cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
    string str = "hello world, world is great";
    string oldSub = "world", newSub = "earth";
    size_t pos = 0;
    while ((pos = str.find(oldSub, pos)) != string::npos) {
        str.replace(pos, oldSub.length(), newSub);
        pos += newSub.length();   // 跳过已替换部分，防重复匹配
    }
    cout << "替换后：" << str << endl;
    return 0;
}
为什么 pos += newSub.length()？

若不后移，下一次 find 又会从刚替换的位置开始，可能在同一处反复匹配（尤其新串含旧串时）。后移"已替换长度"可避免死循环与重复替换。

28.3 字符串反转算法

标准库 reverse

reverse_std.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string str = "reverse";
    reverse(str.begin(), str.end());
    cout << "反转结果：" << str << endl;   // esrever
    return 0;
}

手动双指针反转字符数组

reverse_arr.c
#include <stdio.h>
#include <string.h>
int main() {
    char str[] = "abc123";
    int l = 0, r = strlen(str) - 1;
    while (l < r) {
        char t = str[l]; str[l] = str[r]; str[r] = t;
        l++; r--;
    }
    printf("反转：%s\n", str);   // 321cba
    return 0;
}

28.4 字符串分割算法

按分隔符拆分字符串，存入字符串数组：

split_demo.cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
    string str = "apple, banana, orange";
    char delim = ',';
    const int MAX = 10;
    string parts[MAX];
    int cnt = 0; string cur;
    for (char ch : str) {
        if (ch == delim) {
            if (!cur.empty() && cnt < MAX) parts[cnt++] = cur;
            cur.clear();
        } else cur += ch;
    }
    if (!cur.empty() && cnt < MAX) parts[cnt++] = cur;
    for (int i = 0; i < cnt; i++) cout << i + 1 << "：" << parts[i] << endl;
    return 0;
}

28.5 字符串去空格

去除全部空格（C 字符数组）

remove_spaces.c
#include <stdio.h>
#include <string.h>
int main() {
    char str[] = "h e l l o";
    int j = 0;
    for (int i = 0; str[i] != '\0'; i++)
        if (str[i] != ' ') str[j++] = str[i];
    str[j] = '\0';
    printf("去空格：%s\n", str);   // hello
    return 0;
}

仅去除首尾空格

trim_spaces.c
#include <stdio.h>
#include <string.h>
int main() {
    char str2[] = "  hello world  ";
    int len = strlen(str2);
    int start = 0, end = len - 1;
    while (start <= end && str2[start] == ' ') start++;   // 找首个非空格
    while (end >= start && str2[end] == ' ') end--;       // 找末个非空格
    int k = 0;
    for (; start <= end; k++, start++) str2[k] = str2[start];
    str2[k] = '\0';
    printf("去首尾空格：%s\n", str2);   // "hello world"
    return 0;
}
原文档易错点

判断空格要用字符常量 ' '（单引号），不能用空字符串 "" 或空字符 '\0'。写成 str2[start] == '' 是语法错误。

28.6 大小写转换

字符 c：

  • 转大写：c - 32（小写 az：97122，大写 AZ：6590）
  • 转小写：c + 32
case_conv.c
#include <stdio.h>
int main() {
    char ch = 'a';
    ch -= 32;          // 'a'->'A'
    putchar(ch);
    return 0;
}
用 <cctype> 更安全

char 可能是有符号类型，直接 c - 32 处理非字母字符会出问题。竞赛中推荐用 toupper/tolower（见第 25 章 25.5.3），它们只对字母生效，更安全。

28.7 选择题练习

1. C++ string::find 在找不到子串时返回？

A. -1
B. 0
C. string::npos
D. 抛出异常

点击展开参考答案与解析

答案：C

解析：string::find 找不到时返回 string::npos（一个很大的无符号值），不是 -1，选 C。

2. 暴力匹配中，主串 ababc 查找子串 abc，首次命中位置（下标）是？

A. 0
B. 1
C. 2
D. 3

点击展开参考答案与解析

答案：C

解析：主串 a b a b c，子串 a b c：i=0(abc≠aba)、i=1(bab≠abc)、i=2(abc= abc) 命中，下标 2，选 C。

3. 下面哪个函数可以反转一个 string？

A. strlen
B. std::reverse
C. strcpy
D. find

点击展开参考答案与解析

答案：B

解析：std::reverse(str.begin(), str.end()) 可反转 string，选 B。strlen 求长度、strcpy 复制、find 查找。

4. 关于字符串替换时 pos += newSub.length()，其目的是？

A. 加快查找速度
B. 跳过已替换部分，避免重复匹配
C. 统计替换次数
D. 修正长度错误

点击展开参考答案与解析

答案：B

解析：后移"已替换长度"是为了跳过刚替换的部分，防止在同一处重复匹配甚至死循环，选 B。

5. 判断字符 ch 是否为空格，正确写法是？

A. ch == ""
B. ch == '\0'
C. ch == ' '
D. ch == " "

点击展开参考答案与解析

答案：C

解析：空格是字符，应用字符常量 ' '（单引号），选 C。"" 是字符串、'\0' 是结束符，都不对。

SShowball OI知识手册