0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 算法精解:最长公共子序列

morixinguan 2016-06-29 10:31:00 浏览394

```int CommonOrder(int m, int n, int x[ ] , int y[ ] , int z[ ])
{
int i , j , k ;
for (j = 0; j <= n; j ++ ) // 初始化第 0 行
L[0][j] = 0;
for (i = 0; j <= m; i++ ) // 初始化第 0 列
L[i] [0] = 0;
for (i = 1; i<= m; i++ )
for (j = 1; j <= n; j++ )
if (x[i] == y[j]) { L[i][j] = L[i - 1] [j - 1] + 1; S[i][j] = 1; }
else if (L[i][j - 1] >= L[i - 1][j] ) { L[i][j] = L[i] [j - 1]; S[i][j] = 2; }
else {L[i][j] = L[i - 1][j]; S[i][j] = 3; }
i = m; j = n; k = L[m] [n];
while(i > 0 && j > 0)
{
if (S[i][j] == 1) { z[k] = x[i] ; k -- ; i -- ; j -- ; }
else if (S[i][j] == 2) j -- ;
else i -- ;
}
return L[m][n] ;
}

int main(void)
{
int i,j;
int x[10] ;
int y[10] ;
int z[10] ;
i = CommonOrder(10,10,x,y,z) ;
printf("%d\n",i) ;
putchar('\n');
for(i = 0 ; i < 10 ; i++){
for(j = 0 ; j < 10 ; j++){
printf("%d ",L[i][j]);
}
putchar('\n');
}

return 0 ;
}```

2

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2

morixinguan
+ 关注