字符串的匹配

时间限制: 1 Sec 内存限制: 128 MB

题目描述

相信大家都做许多的字符串匹配问题了，一天，503集训室的俊哥突然想出了新点子。现在给你两个字符串a,b求最长公共子串。对于是字符串匹配大师的你来说，这个再简单不过了。但是，如果现在你有k次修改机会，每次你都可以选择其中某个串的某个位置。将其修改成任意字符。

你需要合理使用这k次修改机会，使得修改后字符串的最长公共子串最长。相信这个对于你来说也很简单。

输入

题目中有多组数据，每组数据的第一行为一个整数k。表示修改次数。

输入数据的第二行和第三行是a,b两个字符串。题目保证每个串的长度不超过500。

输出

输出每一行为一个整数，表示修改后的两个串的最长公共子串长度。

样例输入

0
abcde
jcdkl
2
aaaaa
ababa

样例输出

2
5
分析：给两个字符串，有k次修改机会，问能得到的最大公共子串多长？
　　　　　　参考本校大牛做法：
　　　枚举两个串的起始对应位置，dp维护到当前点所需修改次数，pre维护第k次修改的位置，复杂度O（N*N）；
代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=(int)m;i<=(int)n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
#define intxt freopen("in.txt","r",stdin)
const int maxn=1e5+10;
using namespace std;
int gcd(int p,int q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k,t,pre[maxn],dp[maxn],ans;
char a[maxn],b[maxn];
int main()
{
    int i,j;
    while(~scanf("%d",&k))
    {
        ans=0;
        scanf("%s%s",a+1,b+1);
        int len1=strlen(a+1),len2=strlen(b+1);
        for(i=1;i<=len1;i++)
        {
            int cnt=0,p1=i,p2=1;
            while(p1<=len1&&p2<=len2)
            {
                if(a[p1]==b[p2])
                {
                    dp[p2]=dp[p2-1];
                }
                else
                {
                    dp[p2]=dp[p2-1]+1;
                    pre[++cnt]=p2;
                }
                if(dp[p2]<=k)ans=max(ans,p2);
                else ans=max(ans,p2-pre[dp[p2]-k]);
                p1++,p2++;
            }
        }
        for(i=1;i<=len2;i++)
        {
            int cnt=0,p1=1,p2=i;
            while(p1<=len1&&p2<=len2)
            {
                if(a[p1]==b[p2])
                {
                    dp[p1]=dp[p1-1];
                }
                else
                {
                    dp[p1]=dp[p1-1]+1;
                    pre[++cnt]=p1;
                }
                if(dp[p1]<=k)ans=max(ans,p1);
                else ans=max(ans,p1-pre[dp[p1]-k]);
                p1++,p2++;
            }
        }
        printf("%d
",ans);
    }
    //system("Pause");
    return 0;
}