作者：岁月无言0106 | 来源：互联网 | 2023-12-10 09:07
本文介绍了求解最长公共子串问题的方法，并提供了一个具体的应用场景。最长公共子串是指两个字符串中最长的连续子串，本文通过给定两个字符串和修改次数，探讨了如何合理利用修改次数来使得最长公共子串达到最大长度。该问题在字符串处理中具有广泛的应用价值。
题目描述
所谓最长公共子串，比如串$A:"abcde"$，串$B:"jcdkl"$，则它们的最长公共子串为串$"cd"$，即长度最长的字符串，且在两个串中都作为连续子串出现过。
给定两个长度都为RnR的字符串，对于字符串大师的你来说，求它们的最长公共子串再简单不过了。
所以现在你有$k$次修改机会，每次你可以选择其中某个串的某个位置，将其修改成任意字符。
你需要合理使用这$k$次修改机会，使得修改之后两个串的最长公共子串最长。相信对于字符串大师的你来说，这个问题也难不倒你。
输入格式
第一行包含两个整数$n,k$，分别表示字符串的长度和修改次数。
第二行包含一个长度为$n$的仅由小写字符构成的字符串$S$。
第三行包含一个长度为$n$的仅由小写字符构成的字符串$T$。
输出格式
输出一行一个整数，即修改完毕之后两个串的最长公共子串的长度。
样例
样例输入1：
5 0
abcde
jcdkl
样例输出1：
2
样例输入2：
5 2
aaaaa
ababa
样例输出2：
5
数据范围与提示
对于$100\%$的数据，$0\leqslant k\leqslant n$。
题解
难得的水题，可是我出去玩去了，所以没考……
疯回来看题，有点难，不会……
然后我看了数据范围，这不**题嘛……
于是$5$分钟就切了。
然后我知道好多人都打的$DP$，其实暴力就可以。
我们肯定是连着好几个不匹配的时候使用修改机会，所以我们可以枚举两个串的起点，然后逐位比较，不一样就把机会用掉，知道没有修改或者到头了为止。
讲个故事，$skyh$看到这道题打了个$DP$，然后想打个暴力对拍一下，打完发现时间复杂度是一样的，这很尴尬，故事讲完了……
所以看到简单题千万不要想复杂。
时间复杂度：$\Theta(n^3)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include
using namespace std;
int n,k;
char S[301],T[301];
int l,r,sum;
int ans;
int main()
{
scanf("%d%d%s%s",&n,&k,S+1,T+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
l=i;
r=j;
sum=0;
while(l&&r&&sum<=k)
{
if(S[l]!=T[r])sum++;
l--;
r--;
}
if(sum>k)ans=max(ans,i-l-1);
else ans=max(ans,i-l);
}
printf("%d",ans);
return 0;
}
rp++
京公网安备 11010802041100号