当前位置:网站首页>Mengxin summary of LCs (longest identical subsequence) topics
Mengxin summary of LCs (longest identical subsequence) topics
2022-07-05 08:51:00 【Qizi K】
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;
}
边栏推荐
- OpenFeign
- 319. 灯泡开关
- Redis实现高性能的全文搜索引擎---RediSearch
- Numpy pit: after the addition of dimension (n, 1) and dimension (n,) array, the dimension becomes (n, n)
- kubeadm系列-01-preflight究竟有多少check
- Halcon color recognition_ fuses. hdev:classify fuses by color
- Redis implements a high-performance full-text search engine -- redisearch
- Adaboost使用
- Apaas platform of TOP10 abroad
- 多元线性回归(梯度下降法)
猜你喜欢
Programming implementation of ROS learning 5-client node
Halcon shape_ trans
C# LINQ源码分析之Count
资源变现小程序添加折扣充值和折扣影票插件
Guess riddles (11)
Halcon affine transformations to regions
Run菜单解析
TF coordinate transformation of common components of ros-9 ROS
Halcon: check of blob analysis_ Blister capsule detection
Mathematical modeling: factor analysis
随机推荐
How apaas is applied in different organizational structures
Use and programming method of ros-8 parameters
How to manage the performance of R & D team?
Beautiful soup parsing and extracting data
Golang foundation - the time data inserted by golang into MySQL is inconsistent with the local time
ROS learning 1- create workspaces and function packs
猜谜语啦(2)
EA introduction notes
Several problems to be considered and solved in the design of multi tenant architecture
Halcon color recognition_ fuses. hdev:classify fuses by color
asp.net(c#)的货币格式化
Tips 1: Web video playback code
Array,Date,String 对象方法
猜谜语啦(8)
Run菜单解析
[daiy4] copy of JZ35 complex linked list
Ros-11 common visualization tools
多元线性回归(梯度下降法)
One dimensional vector transpose point multiplication np dot
Halcon shape_ trans