アルゴリズム導論最長共通サブシーケンス(自分の考えで書いたもの)
1429 ワード
#include
#include
#include
int getlastPos(char *s,char c,int pos)
{
int len=strlen(s),i;
for(i=pos-1;i>=0;i--)
{
if(c==s[i])
return i;
}
return i;
}
int** initM(char *x,char *y)
{
int xlen=strlen(x);
int ylen=strlen(y);
int i,j;
//m[i][0]: x[i] DP, x[i] , x i y
//m[i][1]: x i
//m[i][2]: x[i]
int **m=(int **)malloc(xlen*sizeof(int*));
for(i=0;i=0;i--)
{
m[i][0]=getlastPos(y,x[i],ylen);
if(m[i][0]!=-1)
m[i][1]=1;
else
m[i][1]=0;
for(j=i+1;j=0 && m[j][1]+1>m[i][1])
{
m[i][0]=pos;
m[i][1]=m[j][1]+1;
m[i][2]=j;
}
}
}
return m;
}
void printM(int **m,int xlen,int ylen,char *x)
{
for(int i=0;imax)
max=m[i][1];
}
printf("%d
",max);
//printM(m,strlen(x),3,x);
printResult(m,strlen(x),max,x);
getchar();
}