最长公共子序列和最长公共子串模板（LCS）

意思

就是求两个字符串的最长公共子序列

模板1.求最长公共子序列个数

1.用dp来求最长公共子序列个数

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int dp[1000][1000];
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		string a,b;
		cin>>a>>b;
		a=a,b=b;
		int m,n;
		m=a.size(),n=b.size();
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(a[i-1]==b[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
				else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		 }
		 cout<<dp[m][n]<<endl; 
	}
	return 0;
}

2.用双指针模拟求最长公共子序列个数

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
string s1,s2;
int n,T,m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>s1>>s2;
        n=s1.size();m=s2.size();
        s1=' '+s1,s2=' '+s2;
        int ans=0;
        for(int i=1;i<=m;i++){
            int l=1,r=i;
            while(l<=n&&r<=m){
                if(s1[l]==s2[r])r++;
                l++;
            }
            ans=max(ans,r-i);
        } 
        cout<<ans<<"\n";
    }
    return 0;
}

我觉得这个代码有一些问题，比如给你两个字符串a（abcefg），b（cde），你输入时先输入a再输入b跟先输入b再输入a结果不一样，一个正确一个错误，读者自选看或不看

模板2.求最长公共子序列

这个是用dp来求

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define first fi
#define second se
using namespace std;
const int N = 1e5+5;
int a[N],b[N],dp[3005][3005];
void solve ()
{
	string s,s1; cin>>s>>s1;
	s=" "+s;s1=" "+s1;//保证从1开始遍历
	int len=s.size()-1,len1=s1.size()-1;
	for (int i=1;i<=len;i++)
	{
		for (int j=1;j<=len1;j++)
		if (s[i]==s1[j])
		dp[i][j]=dp[i-1][j-1]+1;
		else 
		dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	}//基本模板
//	cout<<dp[len][len1];
	char ans[3005];//这里要用char类型方便赋值
	int i=len,j=len1;
	ans[dp[len][len1]+1]='\0';//给边界加个终止条件
	while (dp[i][j])
	{
		if (s[i]==s1[j])
		{
			ans[dp[i][j]]=s[i];
			i--,j--;
		}
		else 
		{
			if (dp[i][j]==dp[i-1][j])i--;
			else j--;
		}
	}
	cout<<ans+1;///输出的时候加个1可以略过' ';
}

signed main ()
{
	IOS;
	int T =1;
//	cin>>T;
	while(T--) solve ();
	return 0;
}

模板3.求最长公共子串个数

用dp来求

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int dp[1000][1000],ma=0;
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		 string a,b;
		 cin>>a>>b;
		 for(int i=1;i<=a.size();i++)
		 {
		 	for(int j=1;j<=b.size();j++)
		 	{
		 		if(a[i-1]==b[j-1])
		 		dp[i][j]=dp[i-1][j-1]+1;
		 		ma=max(ma,dp[i][j]);
			 }
		 }
		 cout<<ma<<endl;
	}
	return 0;
}