首页 > 算法 > 最长公共子序列LCS-算法回顾

最长公共子序列LCS-算法回顾

2013年4月29日 发表评论 阅读评论 1404次阅读    

最长公共子序列(lcs) 有些变种,比如最长递增子序列,求最小编辑距离;
类似vimdiff等也用的lcs基本原理,猜测可能是这样的:先按行求LCS,或者说编辑距离,然后对需要“编辑”的地方按行求编辑距离。

#include <stdio.h>
#include <string.h>
//gcc  -std=c99 lcs.c 


int lcs( char *s1, char* s2, char*outstr ){
    int len1 = strlen(s1), len2 = strlen(s2);
    int common[len1][len2] ;
    int target[len1][len2] ;
    for(int i=0; i< len1; ++i){//依次求出第一个字符串的从0-len1长度,跟第二个字符串的不同长度之间的LCS
        for(int j=0; j < len2; ++j) {//从前到后,利用之前计算的结果。
            if(s1[i] == s2[j]){//尾部的2个字符串相等,递增长度
                common[i][j] = common[i-1][j-1] + 1 ;
                target[i][j] = 0 ;
            }
            else if( common[i-1][j] < common[i][j-1]){
                common[i][j] = common[i][j-1] ;
                target[i][j] = 1 ;
            }
            else {
                common[i][j] = common[i][j-1] ;
                target[i][j] = -1 ;
            }
        }       
    }
    int tmp = 0;--len1; --len2 ;
    while(1){
        if(len1 < 0 || len2 < 0) break ;
        if(target[len1][len2] == 0){
            outstr[tmp++] = s1[len1] ;
            --len1 ;--len2;
        }
        else if( target[len1][len2] == 1)
            --len2 ;
        else --len1 ;
    }
    outstr[tmp] = 0;
    return tmp ;
}

int main(int argc, char* argv[]) {
    char *str1 = "abcdefg" ;
    char *str2 = "abdefg" ;
    char out[1024] ;
    printf("hello kulv\n");
    int len = lcs( str1, str2, out);
    printf("lcs len=%d\nnreversed longest common string:%s\n", len, out);
}
Share
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

注意: 评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。例如, ABC是本文的评论者之一,则使用'@ABC '(不包括单引号)将会自动将您的评论发送给ABC。使用'@all ',将会将评论发送给之前所有其它评论者。请务必注意user必须和评论者名相匹配(大小写一致)。