infoarena

#include<iostream>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
ifstream in("in.in");
vector<vector<int> >v;
string s1,s2;
//calculeaza cel mai lung subsir comun
//dar  nu si cel mai mare valoare care o cere in problema
void dinamic(){
    int i,j;
    //construirea matricei pe baza recurente programari dinamice
    for(i=1;i<s1.size()+1;i++)
        for(j=1;j<s2.size()+1;j++){
            if(s1[i-1]==s2[j-1])
                v[i][j]=1+v[i-1][j-1];
            else
                v[i][j]=max(v[i-1][j],v[i][j-1]);
        }
    i--;j--;
    //gasirea subsirului de lungime maxima
    while(i>0||j>0){
        if(i>0&&j>0&&s1[i-1]==s2[j-1]){
            cout<<s1[i-1]<<" ";
            i--;j--;
            continue;
        }
        if(i&&v[i][j]==v[i-1][j]){
            i--;
            continue;
        }
        if(j&&v[i][j]==v[i][j-1])
            j--;
    }
    cout<<"\n";
    for(i=1;i<s1.size()+1;i++){
        for(j=1;j<s1.size()+1;j++)
            cout<<v[i][j]<<" ";
        cout<<"\n";
    }
}
int main (){
    in>>s1>>s2;
    v.resize(s1.size()+1);
    int i;
    for(i=0;i<s1.size()+1;i++){
        v[i].resize(s2.size()+1);
    }
    dinamic();
    return 0;
}