アルゴリズム導論最長共通サブシーケンス(自分の考えで書いたもの)

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(); }