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

知识点：字符串、双指针、分类讨论。

解题思路

长度差超过1立即失败。等长时最多允许一个不同位置；相差1时用双指针，只允许在较长串中跳过一个字符。

为什么正确

一次替换只能改变一个等长位置，一次增删只能造成一个对齐偏移，两个分支正好覆盖允许的修改。

易错点

两个串完全相同也属于similar；较长串末尾多出的字符同样计入一次跳过。

复杂度

每组时间O(len(a)+len(b))，空间O(len(a)+len(b))。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        string a,b;
        cin>>a>>b;
        if(a.size()<b.size())swap(a,b);
        bool ok=true;
        if(a.size()>b.size()+1)ok=false;
        else if(a.size()==b.size()) {
            int c=0;
            for(int i=0;i<(int)a.size();i++)c+=a[i]!=b[i];
            ok=c<=1;
        }
        else {
            int i=0,j=0,c=0;
            while(i<(int)a.size()) {
                if(j<(int)b.size()&&a[i]==b[j]) {
                    i++;
                    j++;
                }
                else {
                    i++;
                    c++;
                }
            }
            ok=c<=1;
        }
        cout<<(ok?"similar":"not similar")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。