#include<iostream>
#include<string.h>
#define m 20
int arr[m][m];
using namespace std;
int fun(char st1[],char st2[],int low1,int low2,int high1,int high2)
{
if(arr[low1][low2]!=-1)
return arr[low1][low2];
if((low1>high1)||(low2>high2))
return 0;
if(st1[low1]==st2[low2])
{
arr[low1][low2]=1+fun(st1,st2,low1+1,low2+1,high1,high2);
return arr[low1][low2];
}
else
{
arr[low1+1][low2]=fun(st1,st2,low1+1,low2,high1,high2);
arr[low1][low2+1]=fun(st1,st2,low1,low2+1,high1,high2);
arr[low1][low2]=max(arr[low1+1][low2],arr[low1][low2+1]);
}
return arr[low1][low2];
}
int main()
{
char st1[] = "ABCDGH" ;
char st2[] = "AEDFHR" ;
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
arr[i][j]=-1;
}
}
cout<<fun(st1,st2,0,0,strlen(st1)-1,strlen(st2)-1)<<" is the max commmon subseq.\n";
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZy5oPgojZGVmaW5lIG0gMjAKaW50IGFyclttXVttXTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IGZ1bihjaGFyIHN0MVtdLGNoYXIgc3QyW10saW50IGxvdzEsaW50IGxvdzIsaW50IGhpZ2gxLGludCBoaWdoMikKewoJaWYoYXJyW2xvdzFdW2xvdzJdIT0tMSkKCSAgIHJldHVybiBhcnJbbG93MV1bbG93Ml07CglpZigobG93MT5oaWdoMSl8fChsb3cyPmhpZ2gyKSkKCSAgIHJldHVybiAwOwoJaWYoc3QxW2xvdzFdPT1zdDJbbG93Ml0pCgl7CgkJYXJyW2xvdzFdW2xvdzJdPTErZnVuKHN0MSxzdDIsbG93MSsxLGxvdzIrMSxoaWdoMSxoaWdoMik7CgkJcmV0dXJuIGFycltsb3cxXVtsb3cyXTsKCX0KCWVsc2UKCXsKCQlhcnJbbG93MSsxXVtsb3cyXT1mdW4oc3QxLHN0Mixsb3cxKzEsbG93MixoaWdoMSxoaWdoMik7CgkJYXJyW2xvdzFdW2xvdzIrMV09ZnVuKHN0MSxzdDIsbG93MSxsb3cyKzEsaGlnaDEsaGlnaDIpOwoJCWFycltsb3cxXVtsb3cyXT1tYXgoYXJyW2xvdzErMV1bbG93Ml0sYXJyW2xvdzFdW2xvdzIrMV0pOwoJfQoJcmV0dXJuIGFycltsb3cxXVtsb3cyXTsKfQppbnQgbWFpbigpCnsKICBjaGFyIHN0MVtdID0gIkFCQ0RHSCIgOwogIGNoYXIgc3QyW10gPSAgIkFFREZIUiIgOwoJZm9yKGludCBpPTA7aTxtO2krKykKCXsKCQlmb3IoaW50IGo9MDtqPG07aisrKQoJCXsKCQkJYXJyW2ldW2pdPS0xOwoJCX0KCX0KCWNvdXQ8PGZ1bihzdDEsc3QyLDAsMCxzdHJsZW4oc3QxKS0xLHN0cmxlbihzdDIpLTEpPDwiIGlzIHRoZSBtYXggY29tbW1vbiBzdWJzZXEuXG4iOwoJcmV0dXJuIDA7Cn0=