CF1506C双端字符串问题的解释
CF1506C双端字符串问题的解释
Content
有两个字符串\(a，b\)。我们可以在每次操作中删除两个字符串之一(可以将某个字符串通过若干次操作变为空串)的第一个或最后一个字符。需要多少次操作才能使\(a，b\)两个字符串相同？
数据范围：\(t\) 组数据，\(1\leqslant t\leqslant 100\)，\(1\leqslant |a|,|b|\leqslant 20\)。
Solution
我们发现只要你能找到\(a，b\)两个字符串之间的公共部分，你只需要删除除了这个公共部分之外的其他部分，所以这个问题本质上是要求我们找到\(a，b\)的最长公共子串的长度。而且因为\(a，b\)的长度很小，所以我们考虑直接枚举。
首先，枚举两个字符串中的子字符串的起始位置，然后枚举长度。然后，使用STL中的substr函数提取两个字符串的子字符串。如果两个子串相等，比较前面的答案，选择较大的长度。让我们最终得到的最长公共子串是\(s\)，那么答案就是\(|a| |b|-2\cdot|s|\)。
Code
字符串a，b；
int main(){ 0
MT {
CIN a；int len 1=a . size()；CIN b；int len 2=b . size()；
int ans=0；
F(int，I，0，len1 – 1) F(int，j，0，len2 – 1) F(int，k，0，len1 – i) F(int，l，0，len 2-j){ 0
if(k！=l)继续；//连长度都不一样。这两个子串肯定是不一样的。跳过。
字符串s1=a.substr(i，k)，s2=b.substr(j，l)；
if(s1==s2) ans=max(ans，(int)S1 . size())；
}
println(len 1 len 2-ans * 2)；
}
返回0；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/147915.html