1. 程序设计竞赛中的字符串处理基础
字符串处理是程序设计竞赛中最基础也是最重要的技能之一。在各类算法竞赛中,字符串相关的题目占比高达30%以上。本章将深入解析《深入浅出程序设计竞赛(基础篇)》第六章的核心内容,通过6个典型例题,带你掌握C++字符串处理的精髓。
1.1 字符与字符串基础操作
字符是构成字符串的基本单元,理解字符的底层表示是处理字符串的关键。在C++中,字符实际上是按照ASCII码存储的整数。例如,大写字母'A'的ASCII码是65,小写字母'a'是97,数字'0'是48。
cpp复制// 写法一:使用字符数组和scanf
char s[110];
scanf("%s", s);
for (int i = 0; s[i] != '\0'; i++) {
if ('a' <= s[i] && s[i] <= 'z') {
s[i] = s[i] - 'a' + 'A'; // 小写转大写
}
}
printf("%s\n", s);
这段代码展示了最基本的字符大小写转换方法。关键在于理解字符间的算术运算:'a'-'a'+'A'实际上就是97-97+65=65,即'A'的ASCII码。
提示:在竞赛编程中,通常使用C风格的字符数组而非C++的string类,因为前者处理速度更快,内存占用更可控。
1.2 字符输入输出的多种方式
除了常见的scanf/printf,C++还提供了多种字符I/O方法:
cpp复制// 写法二:使用getchar/putchar逐个字符处理
char s;
while (1) {
s = getchar();
if (s == EOF) break;
if ('a' <= s && s <= 'z') {
s = s + 'A' - 'a'; // 另一种转换方式
}
putchar(s);
}
这种方式的优势在于可以处理包含空格的输入,而scanf的%s会在遇到空格时停止读取。在竞赛中,根据题目要求选择合适的I/O方法可以节省大量调试时间。
2. 字符串加密与统计技巧
2.1 凯撒密码的实现
凯撒密码是一种经典的替换加密技术,通过将字母表中的每个字母移动固定位数来实现加密。
cpp复制int n;
char s[60];
scanf("%d %s", &n, &s);
for (int i = 0; s[i]; i++) {
putchar((s[i] - 'a' + n) % 26 + 'a');
}
这段代码的核心算法是(s[i]-'a'+n)%26+'a',它实现了字母的循环移位。例如,对于字母'z'(122)和n=1:
- 'z'-'a' = 25
- 25+1 = 26
- 26%26 = 0
- 0+'a' = 'a'
注意事项:模运算(%)在这里确保了移位后的字母仍然在a-z范围内循环。当n可能很大时,应该先对n取模26,避免整数溢出。
2.2 字母频率统计与质数判断
统计字母出现频率是字符串处理的常见任务,结合质数判断可以解决一些有趣的竞赛题目。
cpp复制char a[110];
int ans[26] = {0}; // 统计a-z的出现次数
int l = strlen(a);
for (int i = 0; i < l; i++) {
ans[a[i] - 'a']++; // 字母到索引的转换
}
int maxn = 0, minn = 10000;
for (int j = 0; j < 26; j++) {
if (ans[j] > maxn) maxn = ans[j];
if (ans[j] != 0 && ans[j] < minn) minn = ans[j];
}
int delta = maxn - minn;
// 质数判断
if (delta < 2) {
printf("No Answer\n0");
} else {
bool isPrime = true;
for (int h = 2; h * h <= delta; h++) {
if (delta % h == 0) {
isPrime = false;
break;
}
}
printf(isPrime ? "Lucky Word\n%d\n" : "No Answer\n0", delta);
}
这段代码有几个关键点:
- 使用ans[26]数组统计各字母出现次数,通过
a[i]-'a'将字母映射到0-25的索引 - 质数判断时只需检查到√delta即可,这是竞赛中常用的优化技巧
- 对delta=0或1的特殊情况提前处理,避免不必要的计算
3. 字符串操作的高级技巧
3.1 多行输入处理与字符串格式化
处理多行输入是竞赛中的常见需求,特别是当输入格式不规则时。
cpp复制int n, a, b, c;
char last, s[20], ans[20];
scanf("%d\n", &n);
while (n--) {
fgets(s, sizeof(s), stdin); // 读取整行
if (s[0] == 'a' || s[0] == 'b' || s[0] == 'c') {
last = s[0];
s[0] = ' '; // 替换操作符为空格
}
sscanf(s, "%d %d", &a, &b); // 从字符串读取数字
switch (last) {
case 'a': c = a + b; sprintf(ans, "%d+%d=%d", a, b, c); break;
case 'b': c = a - b; sprintf(ans, "%d-%d=%d", a, b, c); break;
case 'c': c = a * b; sprintf(ans, "%d*%d=%d", a, b, c); break;
}
printf("%s\n%d\n", ans, strlen(ans));
}
这段代码展示了几个重要技巧:
- 使用fgets读取整行输入,避免scanf遇到空格就停止的问题
- 使用sscanf从字符串中解析数字,比直接scanf更灵活
- 使用sprintf格式化输出字符串,可以精确控制输出格式
- 通过last变量保存上一步的操作类型,处理省略操作符的情况
实操心得:在竞赛中,输入格式常常不规整,使用fgets+sscanf的组合比直接使用scanf更可靠。记得总是检查fgets的返回值,防止读取失败。
3.2 C++ string类的强大功能
虽然C风格字符数组效率高,但C++的string类提供了更丰富的功能,在非性能关键代码中可以简化开发。
cpp复制string s;
int ans = 0;
while (cin >> s) {
ans += s.length();
}
cout << ans << endl;
这段代码展示了string类的几个特点:
- 自动处理内存分配,不用担心缓冲区溢出
- 流操作符>>会自动跳过空白字符
- length()方法返回字符串实际长度
对于更复杂的字符串操作,string类提供了丰富的方法:
cpp复制string s;
int n, opt, l, r;
cin >> n >> s;
while (n--) {
cin >> opt;
if (opt == 1) { // 后接插入
string a; cin >> a;
s.append(a);
cout << s << endl;
} else if (opt == 2) { // 截取
cin >> l >> r;
s = s.substr(l, r);
cout << s << endl;
} else if (opt == 3) { // 插入
cin >> l;
string a; cin >> a;
s.insert(l, a);
cout << s << endl;
} else { // 查找
string a; cin >> a;
cout << (int)s.find(a) << endl;
}
}
string类的主要方法包括:
- append:字符串拼接
- substr:子串提取
- insert:在指定位置插入
- find:子串查找
性能提示:在需要频繁修改字符串的算法中,string类的操作可能比C风格字符数组慢。对于时间敏感的竞赛题目,建议先用string类实现,如果超时再改为字符数组。
4. 字符串匹配与搜索优化
4.1 不区分大小写的字符串匹配
在实际应用中,经常需要进行不区分大小写的字符串匹配。这需要先将字符串统一转换为小写或大写。
cpp复制string word, s;
getline(cin, word);
getline(cin, s);
// 统一转换为小写
for (char &c : word) {
if ('A' <= c && c <= 'Z') c += 32;
}
for (char &c : s) {
if ('A' <= c && c <= 'Z') c += 32;
}
// 精确匹配(考虑单词边界)
word = ' ' + word + ' ';
s = ' ' + s + ' ';
size_t pos = s.find(word);
if (pos != string::npos) {
// 找到匹配
} else {
// 未找到
}
这段代码的关键点:
- 通过遍历所有字符并检查ASCII码范围实现大小写转换
- 在单词前后添加空格确保完全匹配(避免部分匹配)
- 使用string::find方法进行子串搜索
4.2 字符串处理的常见问题与优化
在实际编程竞赛中,字符串处理常见的问题包括:
- 缓冲区溢出:总是为字符数组分配足够空间(通常比题目要求的最大长度多10-20个字符)
- 未初始化字符串:确保字符数组以'\0'结尾,或者使用memset初始化
- 混用C风格和C++风格I/O:避免同时使用cin/cout和scanf/printf,可能造成缓冲区问题
对于性能敏感的字符串题目,可以考虑以下优化:
- 使用更快的I/O方法(如getchar/putchar代替cin/cout)
- 预分配足够大的字符数组,避免动态分配
- 减少不必要的字符串拷贝,尽量使用指针或引用操作
- 使用KMP等高效字符串匹配算法代替朴素匹配
cpp复制// 快速读取一行(竞赛常用)
char buf[1000010];
fgets(buf, sizeof(buf), stdin);
int len = strlen(buf);
if (buf[len-1] == '\n') buf[--len] = '\0'; // 去除换行符
这段代码展示了竞赛中常用的快速读取方法,比cin.getline更快,且能处理超大字符串。
5. 字符串算法实战技巧
5.1 字符串处理中的边界条件
处理字符串时,边界条件是最容易出错的地方。常见的边界情况包括:
- 空字符串
- 全空格字符串
- 字符串长度等于最大限制
- 包含各种特殊字符的字符串
在编写代码时,应该首先考虑这些边界情况。例如,在统计字符出现次数的题目中:
cpp复制int count[26] = {0};
bool isEmpty = true;
for (int i = 0; s[i]; i++) {
if (isalpha(s[i])) { // 只统计字母
count[tolower(s[i])-'a']++;
isEmpty = false;
}
}
if (isEmpty) {
// 处理空字符串情况
}
5.2 字符串与数值的转换
竞赛中经常需要在字符串和数值之间进行转换。C++提供了多种方法:
cpp复制// 字符串转整数
char numStr[] = "12345";
int num = atoi(numStr); // C风格
// 或者
string s = "12345";
int num = stoi(s); // C++风格
// 整数转字符串
int num = 12345;
char buf[20];
sprintf(buf, "%d", num); // C风格
// 或者
string s = to_string(num); // C++风格
性能比较:atoi/sprintf比stoi/to_string更快,但在现代编译器中差距不大。在时间敏感的场合,可以考虑手写转换函数。
5.3 字符串处理的位运算技巧
对于某些特定问题,位运算可以极大提高字符串处理的效率。例如,判断一个字符串是否所有字符都唯一:
cpp复制bool isUnique(const string& s) {
int mask = 0;
for (char c : s) {
int bit = 1 << (c-'a');
if (mask & bit) return false;
mask |= bit;
}
return true;
}
这种方法利用一个int变量的每一位表示一个字母是否出现过,时间复杂度O(n),空间复杂度O(1)。
6. 竞赛中的字符串题目解题策略
6.1 字符串题目的常见类型
算法竞赛中的字符串题目大致分为以下几类:
- 字符串匹配与搜索
- 字符串变换与操作
- 字符串分析与统计
- 字符串编码与解码
- 字符串与数据结构的结合(如Trie、后缀数组)
针对不同类型的问题,需要采用不同的解题策略。例如,对于字符串匹配问题,朴素算法的时间复杂度是O(nm),而KMP算法可以达到O(n+m)。
6.2 解题步骤与调试技巧
解决字符串题目的通用步骤:
- 仔细阅读题目,明确输入输出格式和边界条件
- 设计算法,考虑时间复杂度和空间复杂度
- 编写代码,注意字符串的初始化和边界处理
- 测试各种边界情况(空串、最大长度、特殊字符等)
调试字符串程序时的常用技巧:
- 打印中间结果,确认字符串内容符合预期
- 检查字符串终止符'\0'是否正确设置
- 使用assert验证关键假设
- 对于越界访问,可以使用工具如AddressSanitizer检测
6.3 性能优化实战
对于大规模字符串处理的题目,性能优化至关重要。以下是一些实测有效的优化方法:
- 减少内存分配:预分配足够大的缓冲区,避免频繁分配释放
- 使用更快的I/O:如用getchar代替cin,用puts代替printf输出简单字符串
- 避免不必要的拷贝:使用指针或引用操作字符串
- 利用局部性原理:顺序访问字符串数据,提高缓存命中率
- 使用位运算代替部分操作:如前文所示的唯一性检查
cpp复制// 快速输出字符串(竞赛常用)
void fastPrint(const char* s) {
while (*s) putchar(*s++);
putchar('\n');
}
这种简单的输出函数比cout或printf更快,在处理大量输出时可以节省可观的时间。
