[NC235624] 牛可乐和最长公共子序列

1
2
3
4
题号：NC235624
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

牛可乐得到了两个字符串 $s$ 和 $t$ ,牛可乐想请聪明的你帮他计算出来，两个字符串的最长公共子序列长度是多少。

最长公共子序列的定义是，子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

输入描述:

输入包含多组数据，请读至文件末尾。

每行包含两个字符串 $s,t$，两个字符串用一个空格字符间隔，单个字符串长度不超过 $5000$。

数据保证所有数据的字符串 $s$ 长度之和与字符串 $t$ 长度之和均不超过 $5000$。

输出描述:

对于每组数据，输出一个整数，代表最长公共子序列的长度。

输入

1
abccde bcee

输出

1
3

说明

1
最长公共子序列长度为 bce，长度为 3。

题解

题目解析

这个题目我使用的是朴素的最长公共子序列求解方法,其时间复杂度是 $O(n^2)$ ,具体过程还是使用动态规划完成.

其状态转移方程为:

其实也很好理解:

s1串的第i个字母如果等于s2串的第i个字母,那么i,i位置的最长公共子序列长度就是i-1,i-1的最长公共子序列长度+1.如果不相等,那么其就需要把它的两类分开计算.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[5010][5010];
int main(){
    string s1,s2;
    while(cin >> s1 >> s2){
        for(int i=0;i<s1.size();i++){
            for(int j=0;j<s2.size();j++){
                if(s1[i] == s2[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout << dp[s1.size()][s2.size()] << endl;
    }
    return 0;
}