LCS

红太狼 2021-11-13 23:56 222阅读 0赞

### LCS ###

*  LCS
 *  LCS+滚动数组
 *  LCS 最长字串输出

# LCS #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    
    /* LCS求解两个字符串的最长公共子序列 状态转移方程： if(a[i]==b[j])dp[i][j]=dp[i-1]dp[j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]) */
    
    int LCS(string a,string b){ 
    	int dp[maxn][maxn]={ 0};
    	int alen = a.size(),blen = b.size();
    	for(int i=1;i<=alen;i++)
    		for(int j=1;j<=alen;j++)
    		if(a[i-1]==b[j-1])dp[i][j]=1+dp[i-1][j-1];
    		else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    	return dp[alen][blen];
    }
    
    int main(){ 
    	string a ="programming",b="contest";
    	cout<<LCS(a,b)<<endl;//输出2
    }

# LCS+滚动数组 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 3e2;
    
    /* LCS求解两个字符串的最长公共子序列 状态转移方程： if(a[i]==b[j])dp[i][j]=dp[i-1]dp[j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]) */
    
    int LCS(string a,string b){ 
    	int dp[2][maxn]={ 0};
    	//使用滚动数组优化空间的时候，是建立在前一层的结果上，需要用到dp[2][n];
    	int alen = a.size(),blen=b.size(),z=0;
    	for(int i=1;i<=alen;i++){ 
    		for(int j=1;j<=blen;j++){ 
    			if(a[i-1]==b[j-1])dp[z][j]=dp[z^1][j-1]+1;
    			else dp[z][j]=max(dp[z^1][j],dp[z][j-1]);
    		}
    		z^=1;
    	}
    	return dp[z^1][blen];
    }
    
    int main(){ 
    	string a,b;
    	while(cin>>a>>b)
    	cout<<LCS(a,b)<<endl;
    }

# LCS 最长字串输出 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    
    /* LCS求解两个字符串的最长公共子序列 状态转移方程： if(a[i]==b[j])dp[i][j]=dp[i-1]dp[j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]) */
    
    string LCS(string a,string b){ 
    	int dp[maxn][maxn]={ 0};//初始化
    	int alen = a.size(),blen=b.size();
    	for(int i=1;i<=alen;i++){ 
    		for(int j=1;j<=blen;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]);
    	}
    	string t ="";
    	int i = alen,j=blen;
    	while(dp[i][j]){ 
    		if(dp[i][j]==dp[i-1][j])i--;
    		else if(dp[i][j]==dp[i][j-1])j--;
    		else if(dp[i][j]>dp[i-1][j-1])i--,j--,t=a[i]+t;
    	}
    	return t;
    }//输出一个最长字串
    
    int main(){ 
        string a,b;
    	//string a="abcfbc",b="abfcab";
        while(cin>>a>>b)
    	cout<<LCS(a,b)<<endl;
    }