牛客 牛可乐和最长公共子序列

链接：https://ac.nowcoder.com/acm/problem/235624
来源：牛客网

题目描述

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

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

输入描述:

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

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

数据保证所有数据的字符串 sss 长度之和与字符串 ttt 长度之和均不超过 500050005000。

输出描述:

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

示例1

输入

复制abccde bcee

abccde bcee

输出

复制3

3

说明

最长公共子序列长度为 bcebcebce，长度为 333。

#include<bits/stdc++.h> using namespace std; string s,t; const int N=5010; int f[N][N]; int main() { while(cin>>s>>t) { int n=s.size(),m=t.size(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i-1]==t[j-1]) { f[i][j]=f[i-1][j-1]+1; }else{ f[i][j]=max(f[i-1][j],f[i][j-1]); } } } cout<<f[n][m]<<endl; } return 0; }