OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
四级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++四级真题 luogu-B3958 [GESP202403 四级] 相似字符串

📅 2025-08-20·✍️ OneCoder·计算中...·⏱️ 8 分钟

GESP C++四级2024年3月真题。本题主要考察字符串处理和比较的基本操作,可以应用函数规范化代码逻辑。难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B3958 [GESP202403 四级] 相似字符串

题目要求

题目描述

对于两个字符串 和 ,如果 可以通过删除一个字符,或插入一个字符,或修改一个字符变成 ,那么我们说 和 是相似的。

比如 可以通过插入一个字符变成 ,可以通过删除一个字符变成 ,也可以通过修改一个字符变成 。因此 和 、、 都是相似的。但 并不能 通过任意一个操作变成 ,因此它们并不相似。

特别地,两个完全相同的字符串也是相似的。

给定 组 ,请你分别判断它们是否相似。

输入格式

第一行一个正整数 。
接下来 行,每行两个用空格隔开的字符串 和 。

输出格式

对组 ,如果他们相似,输出 similar,否则输出 not similar。

输入输出样例 #1

输入 #1

PLAINTEXT6 行
5
apple applee
apple appe
apple bpple
applee bpple
apple apple

输出 #1

PLAINTEXT5 行
similar
similar
similar
not similar
similar

说明/提示

对全部的测试数据,保证 , 和 的长度不超过 ,仅含小写字母。


题目分析

  1. 问题分析
  • 两个字符串相似的条件:完全相同、通过一次删除操作可以相同、通过一次插入操作可以相同、通过一次修改操作可以相同
  1. 核心算法
  • 首先判断两字符串是否完全相同
  • 根据长度差判断可能的操作类型
  • 长度相同: 只能是修改操作
    • 遍历比较对应位置字符,统计不同字符个数,不同字符数不超过1则相似
  • 长度差1: 可能是插入或删除操作
    • 使用双指针技术,较短串指针 和较长串指针 遍历比较。这种情况下,两个字符串的差异只能是插入或删除一个字符。当遇到不同字符时,说明在长串中多出了一个字符,此时让长串指针 前进一步(相当于跳过这个多余字符),短串指针 保持不变,继续比较。如果之后再次遇到不同字符,说明差异超过一处,则不满足相似条件。这种方法可以有效处理插入和删除操作的判断。例如比较 和 时,当 指向第二个 时发现不同, 前进而 不变,最终可以判定为相似。
  • 长度差大于1: 一定不相似
  1. 时间复杂度分析

    • 字符串比较需要 的时间复杂度,其中为较长字符串的长度
    • 没有使用额外的排序等操作
  2. 空间复杂度分析

    • 只使用了常数个额外变量
    • 空间复杂度为

示例代码

C++82 行
#include <iostream>
#include <cmath>
#include <string>

// 判断两个字符串是否相似的函数
// 参数:两个待比较的字符串 a 和 b
// 返回值:如果相似返回true,否则返回false
bool is_similar(std::string a, std::string b) {
    // 如果两个字符串完全相同,直接返回true
    if (a == b) {
        return true;
    }

    // 如果两个字符串长度差大于1,说明需要多次操作才能相同,返回false
    if (std::abs((int)(a.length() - b.length())) > 1) {
        return false;
    }

    // 处理两个字符串等长的情况
    if (a.length() == b.length()) {
        int diff = 0;  // 记录不同字符的个数
        // 遍历字符串,统计不同字符的数量
        // 由于两个字符串等长,可以同时遍历比较对应位置字符
        for (int i = 0; i < a.length(); i++) {
            // 如果对应位置字符不同,增加差异计数
            if (a[i] != b[i]) {
                diff++;
            }
        }
        // 如果不同字符超过1个,说明需要多次修改,返回false
        if (diff > 1) {
            return false;
        }
        return true;
    }

    // 处理字符串长度相差1的情况
    // s指向较短的字符串,l指向较长的字符串
    std::string s = a.length() > b.length() ? b : a;
    std::string l = a.length() > b.length() ? a : b;

    int i = 0;  // 短字符串的索引
    int j = 0;  // 长字符串的索引
    int diff = 0;  // 记录不同字符的个数

    // 使用双指针遍历两个字符串
    while (i < s.length() && j < l.length()) {
        if (s[i] != l[j]) {
            diff++;
            // 如果不同字符超过1个,返回false
            if (diff > 1) {
                return false;
            }
            // 长字符串指针前移,相当于删除了长字符串中的一个字符
            j++;
        } else {
            // 字符相同时,两个指针都前移
            i++;
            j++;
        }
    }
    return true;
}

int main() {
    int T;  // 测试用例数量
    std::cin >> T;

    // 处理每组测试用例
    for (int i = 0; i < T; i++) {
        std::string a, b;
        std::cin >> a >> b;

        // 输出判断结果
        if (is_similar(a, b)) {
            std::cout << "similar" << std::endl;
        } else {
            std::cout << "not similar" << std::endl;
        }
    }
    return 0;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!