Cod sursa(job #1806303)

Utilizator plecinspaniaCapsunar plecinspania Data 15 noiembrie 2016 08:41:36
Problema Seif Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
#define Nmax 1002
using namespace std;
ifstream fin("seif.in");
ofstream fout("seif.out");
int dp[Nmax][Nmax],t,n,k,m;
char a[Nmax],b[Nmax];

inline void Reset()
{
    int i,j;
    for(i=1;i<=Nmax-2;i++)
        for(j=1;j<=Nmax-2;j++)
            dp[i][j]=0;
    for(i=1;i<=Nmax-2;i++)
        a[i]=b[i]=0;
}

void Rezolvare()
{
    int i,j;
    n=strlen(a+1);
    m=strlen(b+1);
    for(i=n;i>=1;i--)
        for(j=m;j>=1;j--)
            if(a[i]==b[j]) dp[i][j]=dp[i+1][j+1]+1;
            else
            dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
    int p1=0,p2=0;
    for(i=1;i<=n-k+1;i++)
        for(j=1;j<=m-k+1;j++)
            if(dp[i][j]>=k&&a[i]==b[j]&&a[p1]<a[i])
                p1=i,p2=j;
    fout<<a[p1];
    i=p1+1;
    for(    ;i<=n;i++)
    {
        j=p2+1;
        for(    ;j<=m;j++)
            if(a[i]==b[j])
            {
                fout<<a[i];
                p2=j;
                j=Nmax;
            }
    }
    fout<<"\n";
}

void Citire()
{
    int pas;
    fin>>t;
    for(pas=1;pas<=t;pas++)
    {
        Reset();
        fin>>k>>(a+1)>>(b+1);
        Rezolvare();
    }
    fin.close();
    fout.close();
}

int main()
{
    Citire();
    return 0;
}