计算机算法基础——最长公共字符串子序列”问题的动态规划法算法

转自http://hi.baidu.com/%C4%C7%C4%BE%B4%ED%B5%C4%C1%B0%E4%F4/blog/item/d6784f3088b5fcb8d0a2d3ec.html

//最长公共字符串子序列”问题的动态规划法算法


#include    "stdio.h"

#include    "stdlib.h"

#include    "string.h"


#define    MAXN    64        //全局最大值常量

//:=========================“最长公共字符串子序列”问题的动态规划法算法=========================

//计算两个字符串序列的最长公共子序列的长度函数

int        First_Born_SubStr_Len(char *a,char *b,int substrlen[][MAXN])

{

    int    i,j,m = strlen(a),n = strlen(b);

    for(i = 0;i <= m;i++)

        substrlen[i][0] = 0;

    for(j = 1;j <= m;j++)

        substrlen[0][j] = 0;

    for(i = 1;i <= m;i++)

{

        for(j = 1;j <= n;j++)

            if(a[i - 1] == b[j - 1])

                substrlen[i][j] = substrlen[i - 1][j - 1] + 1;

            else if(substrlen[i - 1][j] >= substrlen[i][j - 1])

                substrlen[i][j] = substrlen[i - 1][j];

            else

                substrlen[i][j] = substrlen[i][j - 1];

    }

    return(substrlen[m][n]);

}

//构造最长公共子序列函数

char    *Build_First_Born_SubStr(char *a,char *b,char str[])

{

    int    k,i = strlen(a),j = strlen(b),array[MAXN][MAXN];

    k = First_Born_SubStr_Len(a,b,array);

    str[k] = '';

    while(k > 0)

{

        if(array[i][j] == array[i - 1][j])

            i --;

        else if(array[i][j] == array[i][j - 1])

            j --;

        else

       {

            str[--k] = a[i - 1];

            i --;

            j --;

        }

    }

    return(str);

}

//测试“最长公共字符串子序列”问题的动态规划法函数

void    Run_SubString()

{

    char    str0[MAXN],str1[MAXN],str2[MAXN];

    printf("输入第一个字符串(长度 < %d)： ",MAXN);

    scanf("%s",&str1);

    printf("输入第二个字符串(长度 < %d)： ",MAXN);

    scanf("%s",&str2);

    printf("其“最长公共字符串子序列” = %s ",Build_First_Born_SubStr(str1,str2,str0));

}

//=========================“最长公共字符串子序列”问题的动态规划法算法=========================


int main(int argc, char* argv[])

{

    //Run_SubString();

    Run_Ikebana();

    printf(" 应用程序运行结束！ ");

    return 0;

}