csp信奥赛C高频考点专项训练之字符串 --【子串查找】相似字符串题目描述对于两个字符串A AA和B BB如果A AA可以通过删除一个字符或插入一个字符或修改一个字符变成B BB那么我们说A AA和B BB是相似的。比如apple \texttt{apple}apple可以通过插入一个字符变成applee \texttt{applee}applee可以通过删除一个字符变成appe \texttt{appe}appe也可以通过修改一个字符变成bpple \texttt{bpple}bpple。因此apple \texttt{apple}apple和applee \texttt{applee}applee、appe \texttt{appe}appe、bpple \texttt{bpple}bpple都是相似的。但applee \texttt{applee}applee并不能 通过任意一个操作变成bpple \texttt{bpple}bpple因此它们并不相似。特别地两个完全相同的字符串也是相似的。给定T TT组A , B A,BA,B请你分别判断它们是否相似。输入格式第一行一个正整数T TT。接下来T TT行每行两个用空格隔开的字符串A AA和B BB。输出格式对组A , B A,BA,B如果他们相似输出similar否则输出not similar。输入输出样例 1输入 15 apple applee apple appe apple bpple applee bpple apple apple输出 1similar similar similar not similar similar说明/提示对全部的测试数据保证1 ≤ T ≤ 100 1 \leq T \leq 1001≤T≤100A AA和B BB的长度不超过50 5050仅含小写字母。思路分析通过长度比较和字符差异计数或删除一个字符来判断两个字符串是否相似。核心逻辑将较长字符串放在a较短字符串放在b通过swap保证a.size() b.size()。若长度相等统计相同位置不同字符个数cnt若cnt 1包含完全相同或仅修改一字符则相似。若长度差为 1尝试删除a的每一个字符若删除后与b相等则相似。若长度差大于 1直接不相似。该思路覆盖了“插入、删除、修改”三种操作以及完全相同的情况。代码实现#includebits/stdc.husingnamespacestd;intt;// 判断 a 和 b 是否相似调用前保证 a.size() b.size()boolcheck(string a,string b){intlenaa.size();intlenbb.size();if(lenalenb){// 长度相等的情况intcnt0;for(inti0;ilena;i){if(a[i]!b[i])cnt;// 统计不同字符个数}if(cnt1)returntrue;// 完全相同或只需一次修改elsereturnfalse;}else{// 长度不等此时 lena lenbif(lena-lenb1)returnfalse;// 长度差大于1不可能一次操作// 长度差恰好为1尝试删除 a 的每个字符for(inti0;ilena;i){string tmpa;tmp.erase(i,1);// 删除第 i 个字符if(tmpb)returntrue;// 删除后与 b 相等则相似}returnfalse;}}intmain(){cint;while(t--){string a,b;cinab;if(a.size()b.size())swap(a,b);// 让 a 成为较长的串if(check(a,b)){coutsimilarendl;}else{coutnot similarendl;}}return0;}功能分析输入处理读入测试用例数t循环读入两个字符串a、b。预处理通过swap保证a长度不小于b简化后续判断。相似判断长度相等时统计不同字符数 ≤1 即相似覆盖“完全相同”和“修改一字符”。长度差为 1 时尝试删除较长串的每个字符若某次删除后等于较短串则相似覆盖“删除”操作同时等价于对较短串的“插入”操作。长度差 1 时直接不相似。输出每组结果输出similar或not similar。复杂度每组最坏情况为长度相等时 O(L) 统计或长度差1时 O(L²) 的删除与比较。由于 L ≤ 50T ≤ 100完全可行。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}