Cod sursa(job #2003288)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 22 iulie 2017 16:13:35
Problema Seif Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<fstream>
#include<cstring>
using namespace std;
int n, m, t, i, j, k, sta, stb;
int na[1005][90], nb[1005][90], d[1005][1005];
char a[1005], b[1005];
ifstream fin("seif.in");
ofstream fout("seif.out");
int main(){
    fin>> t;
    for(; t; t--){
        fin>> k;
        fin>> a + 1;
        n = strlen(a + 1);
        fin>> b + 1;
        m = strlen(b + 1);
        memset(d, 0, sizeof(d));
        memset(na, 0, sizeof(na));
        memset(nb, 0, sizeof(nb));
        for(i = n; i >= 1; i--){
            for(j = m; j >= 1; j--){
                if(a[i] == b[j]){
                    d[i][j] = 1 + d[i + 1][j + 1];
                }
                else{
                    d[i][j] = max(d[i + 1][j], d[i][j + 1]);
                }
            }
        }
        for(i = n; i >= 1; i--){
            for(j = 'A'; j <= 'Z'; j++){
                if(a[i] == j){
                    na[i][j] = i;
                }
                else{
                    na[i][j] = na[i + 1][j];
                }
            }
        }
        for(i = m; i >= 1; i--){
            for(j = 'A'; j <= 'Z'; j++){
                if(b[i] == j){
                    nb[i][j] = i;
                }
                else{
                    nb[i][j] = na[i + 1][j];
                }
            }
        }
        sta = stb = 1;
        do{
            for(i = 'Z'; i >= 'A'; i--){
                if(na[sta][i] != 0 && nb[stb][i] != 0 && d[ na[sta][i] ][ nb[stb][i] ] >= k){
                    k--;
                    sta = na[sta][i] + 1;
                    stb = nb[stb][i] + 1;
                    fout<< (char) i;
                    break;
                }
            }
        }while(i >= 'A');
        fout<<"\n";
    }
    return 0;
}