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

题目描述对于两个字符串 A 和 B如果 A 可以通过删除一个字符或插入一个字符或修改一个字符变成 B那么我们说 A 和 B 是相似的。比如 apple 可以通过插入一个字符变成 applee可以通过删除一个字符变成 appe也可以通过修改一个字符变成 bpple。因此 apple 和 applee、appe、bpple 都是相似的。但 applee 并不能 通过任意一个操作变成 bpple因此它们并不相似。特别地两个完全相同的字符串也是相似的。给定 T 组 A,B请你分别判断它们是否相似。输入格式第一行一个正整数 T。接下来 T 行每行两个用空格隔开的字符串 A 和 B。输出格式对组 A,B如果他们相似输出similar否则输出not similar。输入输出样例输入 #1复制5 apple applee apple appe apple bpple applee bpple apple apple输出 #1复制similar similar similar not similar similar说明/提示对全部的测试数据保证 1≤T≤100A 和 B 的长度不超过 50仅含小写字母。AC代码#includebits/stdc.h using namespace std; int main(){ int T; cinT; string s1,s2; for(int i1;iT;i){ bool f1; int s0; cins1s2; int s11s1.size(); int s22s2.size(); if(abs(s11-s22)1){ coutnot similarendl; continue; } int zcmax(s11,s22); int p0,q0; for(int i1;izc;i){ if(s1[p]!s2[q]){ s; if(s11s22){ q--; } if(s11s22){ p--; } } if(s1){ f0; break; } p; q; } if(f1){ coutsimilarendl; } else{ coutnot similarendl; } } return 0; }