Mengxin summary of LCs (longest identical subsequence) topics

Mengxin about LCS（ Longest identical subsequence ） Summary of topics

LCS It's also a classic DP The problem is ~O（nm） Time complexity of , Scrolling array Optimize space complexity
A.Common Subsequence POJ - 1458
LCS The template question of ~
tips： When reading a string, it is subscript 0 At the beginning , No 1 Oh

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

char str1[1005],str2[1005];
int dp[1005][1005];
int main(){
    
	while(~scanf("%s %s",str1,str2)){
    
		memset(dp,0,sizeof(dp));
		int  len1 = strlen(str1), len2 = strlen(str2);
		for(int i = 1; i <= len1; ++i){
    
			for(int j = 1; j <= len2; ++j){
    
				if(str1[i - 1] == str2[j - 1])	dp[i][j] = dp[i - 1][j - 1] + 1;
				else	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		printf("%d\n",dp[len1][len2]);
	}
	return 0;
}

B.Palindrome POJ - 1159 / Luogu P1435 Back string
tips: Reverse the original string to get another string , Find their longest common subsequence , In this way, we can find the longest number of characters that can form a palindrome .（ Positive and reverse order “ public ” The part of is the palindrome part ）
Be careful POJ 1159 open 5005*5005 Of int It will explode ~ To open short！
In addition, the reverse order string can be used without opening a new array , You can also cycle directly from back to front on the original array .（ Be careful algorithm Inside reverse There is no return value ）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int len;
short dp[5005][5005];
string s1,s2;

int main(){
    
	scanf("%d",&len);
	cin >> s1;
	s2 = s1;
	reverse(s1.begin(), s1.end());
	for(int i = 1; i <= len; ++i){
    
		for(int j = 1; j <= len; ++j)
			if(s1[i - 1] == s2[j - 1])	dp[i][j] = dp[i - 1][j - 1] + 1;
			else	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	}
	printf("%d",len - dp[len][len]);
	return 0;
}
 

In fact, space can be optimized ~ Wanted 01 It's like a backpack ,dp Arrays only use i - 1 Row data ,0-(i-2) Row data is useless . We can use a rolling array to solve the problem ：

Space optimized code ：

//LCS Space optimization 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int len,dp[2][5005],cur,pre;
string s1,s2;

int main(){
    
	scanf("%d",&len);
	cin >> s1;
	s2 = s1;
	reverse(s1.begin(), s1.end());
	cur = 1, pre = 0;
	for(int i = 1; i <= len; ++i){
    
		for(int j = 1; j <= len; ++j)
			if(s1[i - 1] == s2[j - 1])	dp[cur][j] = dp[pre][j - 1] + 1;
			else	dp[cur][j] = max(dp[pre][j], dp[cur][j - 1]);
		swap(cur,pre);
	}
	printf("%d",len - dp[pre][len]);// Notice that it has to be pre! Because I will finish pre and cur In exchange for 
	return 0;
}
 

C.Compromise POJ - 2250
LCS Print sequence ~ Just take the word as a whole , The essence is LCS. May adopt dfs To output , Pay attention only when
ans == dp[x - 1][y - 1] + 1 && ans == dp[x - 1][y] + 1 && ans == dp[x][y - 1] + 1 It is certain to find ~
p.s. This question has multiple groups of input .

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
 
int dp[105][105],len1,len2,cnt;
string str1[105],str2[105],s,road[105];

void dfs(int ans, int x, int y){
    
	if(!x || !y)	return ;
	if(ans == dp[x - 1][y - 1] + 1 && ans == dp[x - 1][y] + 1 && ans == dp[x][y - 1] + 1)	road[ans] = str1[x], dfs(ans - 1,x - 1, y - 1);
	else if(ans == dp[x - 1][y])	dfs(ans,x - 1, y);
	else if(ans == dp[x][y - 1])	dfs(ans, x, y - 1);
}
int main(){
    
	while(cin >> s){
    
		len1 = len2 = 0;
		while(s != "#"){
    
			str1[++len1] = s;
			cin >> s;
		}
		cin >> s;
		while(s != "#"){
    
			str2[++len2] = s;
			cin >> s;
		}
		memset(dp,0,sizeof(dp));
		for(int i = 1; i <= len1; ++i){
    
			for(int j = 1; j <= len2; ++j){
    
				if(str1[i] == str2[j])	dp[i][j] = dp[i - 1][j - 1] + 1;
				else	dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
			}
		}
		dfs(dp[len1][len2],len1,len2);
		cout << road[1];
		for(int i = 2; i <= dp[len1][len2]; ++i)
			cout << " " << road[i];
		putchar('\n');
	}
	return 0;
}