\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{listings}
\begin{document}
\lstset{language=C,frame=single,numbers=left,tabsize=2}
\begin{lstlisting}
#include
#include
#include
int
max(int a, int b)
{
if(a>b) return a;
else return b;
}
void
reconstruct(char *x, char *y,
int table[strlen(x)+1][strlen(y)+1])
{
int n=strlen(x),m=strlen(y),i,j,currentChar;
int maxlcs=table[n][m];
char* lcschar=(char*)malloc((maxlcs+1)*sizeof(char));
*(lcschar+maxlcs)='\0';
currentChar=0;
i=0;
j=0;
while(currentChar
{
if( *(x+i) == *(y+j) )
{
*(lcschar+currentChar)=*(x+i);
currentChar++;
//printf("%c\n",*(x+i));
i++;
j++;
}
else if(table[i+1][j] >= table[i][j+1]) i++;
else j++;
}
printf("%s\n",lcschar);
free(lcschar);
}
int
lcs(char *x,char *y)
{
//printf("%zu\n",strlen(x));
int n=strlen(x), m=strlen(y), i, j, table[n+1][m+1];
for(i=0;i<=n;i++) table[i][0]=0;
for(j=0;j<=m;j++) table[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if( *(x+i) == *(y+j) ) table[i][j]=1+table[i-1][j-1];
else table[i][j]=max(table[i-1][j], table[i][j-1]);
reconstruct(x,y,table);
return table[n][m];
}
void
main()
{
int res=lcs("abdebcbb","adacbcb");
//printf("%d\n",res);
}
\end{lstlisting}
\end{document}
2010年11月10日 星期三
訂閱:
張貼留言 (Atom)
0 意見:
張貼留言