首页 > 代码库 > uva10405-最长公共子序列

uva10405-最长公共子序列

题目链接 http://acm.hust.edu.cn/vjudge/problem/19201

 

解题思路

LCS

 

代码

#include<stdio.h>#include<string.h>#define MAX_LEN 1005char str[MAX_LEN], re[MAX_LEN];int dp[MAX_LEN];int main(){    str[0] = re[0] = 0;     while(gets(str+1) && gets(re+1)) {        memset(dp, 0, sizeof(dp));        int n = strlen(str) - 1;        int m = strlen(re) - 1;        int x;        for(int i=1; i<=n; i++) {            x = dp[0];            for(int j=1; j<=m; j++) {                if(str[i] == re[j]) { int y = dp[j]; dp[j] = x + 1; x = y; }                else { x = dp[j]; dp[j] = dp[j]>dp[j-1]?dp[j]:dp[j-1]; }            }        }        printf("%d\n", dp[m]);    }    return 0;}

 

uva10405-最长公共子序列