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

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

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

题目要求

题目描述

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

比如 $\texttt{apple}$ 可以通过插入一个字符变成 $\texttt{applee}$，可以通过删除一个字符变成 $\texttt{appe}$，也可以通过修改一个字符变成 $\texttt{bpple}$。因此 $\texttt{apple}$ 和 $\texttt{applee}$、$\texttt{appe}$、$\texttt{bpple}$ 都是相似的。但 $\texttt{applee}$ 并不能 通过任意一个操作变成 $\texttt{bpple}$，因此它们并不相似。

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

给定 $T$ 组 $A,B$，请你分别判断它们是否相似。

输入格式

第一行一个正整数 $T$。
接下来 $T$ 行，每行两个用空格隔开的字符串 $A$ 和 $B$。

输出格式

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

输入输出样例 #1

输入 #1

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

输出 #1

similar
similar
similar
not similar
similar

说明/提示

对全部的测试数据，保证 $1 \leq T \leq 100$，$A$ 和 $B$ 的长度不超过 $50$，仅含小写字母。

---

题目分析

1. 问题分析

• 两个字符串相似的条件:完全相同、通过一次删除操作可以相同、通过一次插入操作可以相同、通过一次修改操作可以相同

1. 核心算法

• 首先判断两字符串是否完全相同
• 根据长度差判断可能的操作类型
• 长度相同： 只能是修改操作
  • 遍历比较对应位置字符，统计不同字符个数，不同字符数不超过1则相似
• 长度差1： 可能是插入或删除操作
  • 使用双指针技术，较短串指针 $i$ 和较长串指针 $j$ 遍历比较。这种情况下，两个字符串的差异只能是插入或删除一个字符。当遇到不同字符时，说明在长串中多出了一个字符，此时让长串指针 $j$ 前进一步（相当于跳过这个多余字符），短串指针 $i$ 保持不变，继续比较。如果之后再次遇到不同字符，说明差异超过一处，则不满足相似条件。这种方法可以有效处理插入和删除操作的判断。例如比较 $\texttt{apple}$ 和 $\texttt{applee}$ 时，当 $j$ 指向第二个 $\texttt{e}$ 时发现不同，$j$ 前进而 $i$ 不变，最终可以判定为相似。
• 长度差大于1： 一定不相似

1. 时间复杂度分析
   • 字符串比较需要 $O(n)$ 的时间复杂度，其中$n$为较长字符串的长度
   • 没有使用额外的排序等操作
2. 空间复杂度分析
   • 只使用了常数个额外变量
   • 空间复杂度为 $O(1)$

---

示例代码

#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;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号