【例5.19】字符串判等

GitHub跳转原题关系图返回列表

读入两行字符串,去除其中的空格和回车并将大写字母统一转为小写后,判断两个字符串是否相等。

OJ: roj

题目 ID: 5051

难度:入门

标签:字符串模拟

创建: 2026-10-09 00:24

更新: 2026-10-09 00:24

形式化题目

输入两行由大小写字母和空格组成的字符串。需要判断这两个字符串在删除所有空格,并将所有大写字母转换为小写字母后,是否完全相同。若是则输出 YES,否则输出 NO。

正解

思路

本题的两个关键在于:跨行与空白字符的安全读取、大小写转换的跨语言一致性。

首先是行读取。由于数据字符串可能包含大量空格,甚至存在纯空格行,因此 C++ 不能使用 cin >>(遇空格停止),而必须使用 getline。而在 Python 中,如果直接使用 splitlines(),会带来隐患:splitlines() 额外在 \r、\v、\f、\x85 等特殊控制字符处断行,而 C++ 的 getline 只认 \n。为保证两侧语义严格对齐,Python 侧采用字节模式读取,并通过 sys.stdin.buffer.read().partition(b"\n") 截取前两行。

其次是大小写转换。为避免 C++ tolower 与 Python str.lower() 引入基于 locale 或者全 Unicode 支持导致的行为差异,统一采用显式的 ASCII 折叠。

两行字符串均获取后,遍历它们的字节序列,过滤掉所有的空格字符和可能的行尾 \r,对大写英文字母作转换。最后比较这两个过滤并处理好的字符串,相等输出 YES,否则输出 NO。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 00:03
# update_at: 2026-10-09 00:14

import sys

DROPPED = b" \r"  # 要删掉的字节:空格;以及 CRLF 数据被 C++ getline 留下的行尾 '\r'
FOLD = bytes.maketrans(bytes(range(65, 91)), bytes(range(97, 123)))  # ASCII 'A'-'Z' -> 'a'-'z'


def normalize(line: bytes) -> bytes:
    """删去空格与行尾 '\r',并把 ASCII 大写字母折叠成小写,供两行比较。"""
    return line.translate(FOLD, DROPPED)


def solve() -> None:
    """整行读入两行原文,比较规范化后的字节串是否相同。"""
    raw = sys.stdin.buffer.read()
    # 只按 '\n' 断行:str.splitlines() 还会在单独的 '\r'、'\v'、'\f'、'\x85' 等处断行,
    # 而 C++ getline 只认 '\n',用 splitlines 会与 C++ 侧读到不同的行。
    line_a, _, rest = raw.partition(b"\n")
    line_b, _, _ = rest.partition(b"\n")  # 文件不足两行时 line_b 为空串,与 C++ 的空行等价
    equal = normalize(line_a) == normalize(line_b)
    print("YES" if equal else "NO")


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 00:06
 * update_at: 2026-10-09 00:14
 */
// 一本通 2049《【例5.19】字符串判等》(ROJ 5051)
// 题意:两行,每行只由大小写字母和空格组成;忽略大小写、忽略空格后相等输出 YES,否则 NO。
// 考点:某一行可能整行全是空格 ⇒ 绝不能 cin >> s(会在第 1 个空格处截断),必须整行读入。
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

string line_a; // 第 1 行原文(整行读入,空格原样保留)
string line_b; // 第 2 行原文(整行读入,空格原样保留)

// 读入两行原文。行尾的 '\r' 是 CRLF 数据在 Linux 评测时被 getline 留下的残留,
// 统一在规范化阶段丢弃,与本 skill 对 CRLF 数据的一贯处理一致。
void read_input() {
    getline(cin, line_a);
    getline(cin, line_b);
}

// 返回「删去所有空格与 '\r',并把 ASCII 大写字母折叠成小写」后的规范串。
// 只折叠 'A'..'Z',不受 locale 影响(题面保证每行只由字母和空格组成)。
string normalize(const string& s) {
    string res;
    ll len = s.size();
    for (ll i = 0; i < len; i++) {
        char c = s[i];
        if (c == ' ' || c == '\r') {
            continue;                     // 忽略空格;顺手丢掉 CRLF 的行尾残留
        }
        if (c >= 'A' && c <= 'Z') {
            c += 32;                      // 忽略大小写:ASCII 大写统一转小写
        }
        res += c;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    read_input();
    // 文件只有 0/1 行时对应的那行是空串,normalize 后仍为空串,自然与「空行」等价
    if (normalize(line_a) == normalize(line_b)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

复杂度

  • 时间复杂度:O(n)\mathcal{O}(n),其中 nn 为字符串的长度。
  • 空间复杂度:O(n)\mathcal{O}(n),用于存储去除了空格并转换大小写后的比较结果。

总结

  1. 题意与读法确证:忽略大小写 + 忽略空格后比较,相等输出 YES,否则输出 NO(全大写,行尾无空格)。其中「忽略空格」确切含义是删除所有空格,而非压缩连续空格。这在数据中由 p2、p5、p10 三个判别点直接确证(压缩读法在这三点会判定失败并输出错误的 NO)。
  2. 行读取的跨语言陷阱(已修):
    • Python 的 splitlines() 额外在 \r、\v、\f、\x85 等处断行,而 C++ getline 只认 \n。这会导致分歧,最小分歧例比如:printf 'a\rA\r'(Python 分行取两端比较输出 YES,C++ 当成一整行输出 NO);又如含有行内 \v 的情况 a\x0bA\nx\n。
    • ⚠️ 提示:请勿错误认为 a\rb\r 对 splitlines 是分 3 项,实际上返回 2 项(末尾不补空项)。
    • 修法:改为 sys.stdin.buffer.read().partition(b"\n") 安全划分前两行。
    • 顺带消除的副作用:文本模式下 UTF-8 严格解码在遇到 \x85 时会直接崩溃,同时也避开了 universal-newline 转换。
    • 数据不可达但仍修:虽然实测 10 个数据点全是纯 ASCII 且不含干扰分隔符,但依然采取了修复。理由有三:1. 5048 先例,与 5048 数据情况类似,仓库同样选了「按 \n 切行」的修法,本包应与之一致;2. 风险不在数据在评测机,题面没给字符集/行长上限,未来重造数据或换 CRLF 数据即触碰;3. 顺带消除文本模式的两个副作用。
  3. 大小写折叠改为显式 ASCII:去除了 tolower 和 str.lower() 的 locale 依赖与跨语言两链行为差异,改为显式 ASCII 判断(C++:c >= 'A' && c <= 'Z';Python:bytes.maketrans(65-90 → 97-122))。
  4. 边界情况:
    • p3 出现第 1 行是 100 个空格,第 2 行是空行。虽然「空行 vs 全空格行」在读取时有区别,但规范化后都归约为空串,最终均输出 YES。
    • 只有 1 行或空文件时,两侧语言的行为一致(只有 1 行时均不等并输出 NO,空文件时两侧均输出 YES)。
  5. V1 反事实测试:
    • 不忽略空格:影响 4/10(p2, p3, p5, p10),承重 ✅。
    • 不折叠大小写:影响 4/10(p1, p2, p5, p10),承重 ✅。
    • 不滤行尾 \r:影响 0/10,不承重。worker 如实报告:本数据无 CR;CRLF 格式下两行的 \r 对称出现,也不改变最终比对答案。保留它是为了对齐 5048 与 CRLF 数据读取的稳健性(属离数据承重)。
  6. 验证强度摘要:
    • 异源「边扫边比」(完全不同源算法,遇字母当场折叠提前退出)跑了 605 组(含随机和手造裸CR/VT/FF)数据 ⇒ 原 Python 实现有 10 组分歧、修正后 0 组分歧。
    • 第三条独立路径使用素材源 std.cpp(getchar 逐字符不落缓冲读取)测试真实 10 点四路一致,且随机 500 组 0 分歧。
    • V2 代码中的字面量皆为语义常量;check_bytes.py 逐字节对比真实输出 10/10,确证 YES\n(4 字节)/ NO\n(3 字节)格式正确且无行尾空格。
  7. 跨语言清单检查:行分隔符与空白集编码存在风险(如 splitlines() 的特殊断行),均已被修正。第 2 行为空时,getline 与 b"" 语义一致。