题解：B3958 [GESP202403 四级] 相似字符串

· · 题解

点这里观看更佳
题目传送门

个人觉得此题还行，我不会告诉你我提交了三次。

思路

把删除字符和增加字符两种操作合并成一种，本人没有做任何字符串操作。我分成了以下三种情况：
1.两个字符串长度相等，改变字符串方式只有改变字符串中的字符一种方式，所以只需在两个字符串中寻找不相同字符个数，如果不相同字符数小于等于 1,就可以，否则不行。
2.两个字符串长度相差等于 1，先将长度长度字符串放在第一个，方便操作。只需在两个字符串中遍历，整个标记，在第一个不相同的字符改标记，标记代表第二个字符串中已经有插入过数，以后坐标都改成 i+1。当标记为 1 时，在后面还能找到不同的字符，也是没救的。
3.两个字符串长度相差大于 1，这是没救的。

AC code:

#include <bits/stdc++.h>//万能头
using namespace std;
int main(){
    int n;cin>>n;//输入
    while(n--){
        string a,b;cin>>a>>b;//输入
        if(a.size()<b.size()) swap(a,b);//统一字符串 a 最长，方便操作
        if(a.size()-b.size()>1){//如果长度相差大于 1，无论怎么做都无法一样
            cout<<"not similar"<<endl;
            continue;
        }
        if(a.size()-b.size()==1){//如果相差 1 就统一让字符串 b 增加一个字母
            int ans=0,f=0;//ans 代表 b[i] 当前是否有和 a[i] 不相等
            for(int i = 0;i<b.size();i++){
                if(a[i+ans]!=b[i])ans=1;//如果不相等 ans 就为 1
                if(ans&&a[i+ans]!=b[i]){//如果 ans 已经为 1 了还不相等就没救了
                    cout<<"not similar"<<endl;
                    f=1;
                    break;//要退循环，不然你会看见好多个 not similar
                }
            } 
            if(f==0) cout<<"similar"<<endl;
        }
        if(a.size()==b.size()){//如果长度相等，直接判断 a 和 b 有多少个不相等
            int sum=0;
            for(int i = 0;i<a.size();i++){
                if(a[i]!=b[i]) sum++;//统计有多少个不相等
            }
            if(sum<=1) cout<<"similar"<<endl;//不相等数量小于等于 1 是就可以
            else cout<<"not similar"<<endl;
        }
    }
  return 0;//完结撒花
}

码字辛苦，管理员给过。。。
都看完了，点个赞再走吧 qwq