前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU1159(LCS)

HDU1159(LCS)

作者头像
Enterprise_
发布2019-02-21 17:16:46
3600
发布2019-02-21 17:16:46
举报
文章被收录于专栏:小L的魔法馆
这里写图片描述
这里写图片描述
代码语言:javascript
复制
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
char str1[1000], str2[1000];
int length[1000][1000]; //str1的左边i个字符形成的子串,与str2左边的j个字符形成的子串的最长公共子序列的长度(i, j从0 开始算),
int main(void)
{
    while (cin>>str1>>str2)
    {
        int len_one = strlen(str1), len_two = strlen(str2), i, j;
        for (i = 0; i <= len_one; i++)
            length[i][0] = 0;       //str1前i个字符的字串串,str2为0,字串为0
        for (j = 0; j <= len_two; j++)
            length[0][j] = 0;       //str2前j个字符的字串串,str2为0,字串为0
        for(i=1;i<=len_one;i++)
            for (j = 1; j <= len_two; j++)
            {
                if (str1[i - 1] == str2[j - 1])     //如果两者相等。此时这个字符是两个字符串的一个LCS
                    length[i][j] = length[i - 1][j - 1] + 1;
                else                            //如果两者不等,那么这个字符可能是length[i - 1][j], length[i][j - 1]其中一个的一个LCS
                    length[i][j] = max(length[i - 1][j], length[i][j - 1]);
            }
        cout << length[len_one][len_two] << endl;
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年03月21日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档