最長共通サブシーケンス(印刷可能LCS)
ダイナミックプランニングアルゴリズム
再帰アルゴリズム
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAXSTRLEN 20
int Lcs(char x[], char y[], int path[][MAXSTRLEN])// x y ,path ,
{
int i, j;
int len1=strlen(x)-1;
int len2=strlen(y)-1;
int **c=new int*[len1+1];
for(i=0; i<=len1; i++)
c[i]=new int[len2+1];
for(i=0; i<=len1; i++)
c[i][0]=0;
for(i=0; i<=len2; i++)
c[0][i]=0;
for(i=1; i<=len1; i++)
for(j=1; j<=len2; j++)// x[1],y[1]
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
path[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
path[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
path[i][j]=3;
}
}
return c[len1][len2];
}
void PrintLcs(int i, int j, char x[], int path[][MAXSTRLEN])//
{
if(i==0 || j==0)
return;
if(path[i][j]==1)
{
PrintLcs(i-1, j-1, x, path);
cout<<x[i];
}
else if(path[i][j]==2)
PrintLcs(i-1, j, x, path);
else
PrintLcs(i, j-1, x, path);
}
void main()
{
char a[MAXSTRLEN];
char b[MAXSTRLEN];
int path[MAXSTRLEN][MAXSTRLEN];
gets(a+1);//a[0] , a[1]
gets(b+1);//b[0] , b[1]
cout<<Lcs(a, b, path)<<endl;
cout<<" :";
PrintLcs(strlen(a)-1, strlen(b)-1, a, path);
cout<<endl;
}
再帰アルゴリズム
#include <iostream>
using namespace std;
#define MAXSTRLEN 20
//
int Lcs(char *str1, char *str2)
{
if(*str1=='\0' || *str2=='\0')
return 0;
if(*str1==*str2)
return Lcs(str1+1, str2+1)+1;
else if(Lcs(str1+1, str2)>Lcs(str1, str2+1))
return Lcs(str1+1, str2);
else
return Lcs(str1, str2+1);
}
void main()
{
char a[MAXSTRLEN];
char b[MAXSTRLEN];
gets(a);
gets(b);
cout<<Lcs(a, b)<<endl;
}