随笔 - 87  文章 - 279  trackbacks - 0
<2024年4月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211878
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

最长公共子序列函数 O(n^2)

做 Commen Subsequence 时写的:

int  lcs( char   * x,  char * y)
 {
     int  m  =  strlen(x) + 1 ;
     int  n  =  strlen(y) + 1 ;
     int  record[MAX][MAX];
     int  i, j;

     for  (i = 0 ; i < m; i ++ )
     {
        record[i][ 0 ]  =   0 ;
    }
     for  (j = 0 ; j < n; j ++ )
     {
        record[ 0 ][j]  =   0 ;
    }

     for  (i = 1 ; i < m; i ++ )
     {
         for  (j = 1 ; j < n; j ++ )
         {
             if  (x[i - 1 ]  ==  y[j - 1 ])
             {
                record[i][j]  =  record[i - 1 ][j - 1 ]  +   1 ;
            }
             else
             {
                 if  (record[i - 1 ][j]  >  record[i][j - 1 ])
                 {
                    record[i][j]  =  record[i - 1 ][j];
                }
                 else
                 {
                    record[i][j]  =  record[i][j - 1 ];
                }
            }
        }
    }
     return  record[m - 1 ][n - 1 ];
}
posted on 2006-04-14 20:57 豪 阅读(372) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 豪 Powered by: 博客园 模板提供：沪江博客