#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
char s[MAXN],t[MAXN];
int f[MAXN][MAXN];
int ls,lt;
int main()
{
	scanf("%s",s);//读取字符数组s 
	getchar();//过滤换行符 
	scanf("%s",t);//读取字符数组t 
    ls = strlen(s);//s的字符串长度 
    lt = strlen(t);//t的字符串长度 
    /*for(int i=1;i<=ls;i++)
      printf("%c",s[i]);
    printf("\n");*/
    for(int i=ls;i>=1;i--)  s[i]=s[i-1];
    for(int i=lt;i>=1;i--)  t[i]=t[i-1];
    s[0]='*';
    t[0]='@';
	for(int i=1;i<=ls;i++)
	{
		for(int j=1;j<=lt;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			//如果两个字符相等，才可以作为一个公共字符 
			if (s[i-1]==t[j-1])//注意：字符串的编号是从0开始的 
			{
				f[i][j] = max(f[i][j],f[i-1][j-1]+1);
			}			 
		}
	} 
	printf("%d\n",f[ls][lt]);
	return 0;
}

LCS的一维实现方法：

#include<bits/stdc++.h>
using namespace std;
string a,b;
int la,lb;
int f[300001];
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	
	cin>>a>>b;
	if(a.size()>b.size()) swap(a,b);
	la=a.size();
	lb=b.size();
	for(int i=0;i<la;i++)
	{
		int maxlong=0;
		for(int j=0;j<lb;j++)
		{
			
			int z=maxlong;
			if(b[j]==a[i]) 
			{
				maxlong=max(f[j],maxlong);
				f[j]=z+1;
					
			}
			else
			maxlong=max(f[j],maxlong);
		}
	}
	int ans=0;
	for(int i=0;i<lb;i++)
	ans=max(ans,f[i]);
	cout<<ans-1;
 } 

#include<bits/stdc++.h>
using namespace std;
string s,t;
int f[5001][5001];
int main()
{
	cin>>s;
	cin>>t;
	int ls=s.length()-1;//注意，由于字符串从零读入，这里一定要减一
	int lt=t.length()-1;
	for(int i=1;i<=ls;i++)//注意字符串是从零开始输的，但是我们这里的边界就是第0行，已经初始化为0，所以从第1行开始 
	{
		for(int j=1;j<=lt;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);//ti不在子序列中或sj不在子序列中
			if(s[i-1]==t[j-1])
			{
				f[i][j]=max(f[i][j],f[i-1][j-1]+1);
			} 
		}
	}
	cout<<f[ls][lt];
	return 0; 
}