死嗑最长公共子序列（LCS）

朴灿烈づ我的快乐病毒、 2022-11-21 15:10 133阅读 0赞

### [**【模板】最大公共子序列**][Link 1] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center]  
**半分做法（传统LCS）**

#include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e3+10; //不能写 1e5+10，因为 dp数组相乘 1e9会爆栈，但也因此得不了满分
    int dp[N][N],a[N],b[N];
    
    int main()
    { 
    	int n;cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++) cin>>b[i];
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    		{ 
    			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    			if(a[i]==b[j])
    				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    		}
    	cout<<dp[n][n]<<endl;
    	return 0;
    }

**满分做法（改进LIS）**

#include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    int a[N],b[N],mmp[N],f[N];
    
    int main()
    { 
    	int n;cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++) cin>>b[i];
    	for(int i=1;i<=n;i++) mmp[a[i]]=i;
    	/* for(int i=1;i<=n;i++) { cout<<"a: "<<mmp[a[i]]<<' '<<"b: "<<mmp[b[i]]<<endl; } */ 
    	int len=1;f[1]=mmp[b[1]];
    	for(int i=2;i<=n;i++)
    	{ 
    		if(f[len]<mmp[b[i]]) f[++len]=mmp[b[i]];
    		else
    		{ 
    			int tmp=lower_bound(f+1,f+1+len,mmp[b[i]])-f;
    			f[tmp]=mmp[b[i]];
    		}
    	}
    	/* for(int i=1;i<=len;i++) cout<<f[i]<<' '; */ 
    	cout<<len<<endl;
    	return 0;
    }

**思路**  
一、传统做法（LCS）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 1]  
二、满分做法（改进LIS）  
这种方法比较抽象，举个例子

a = 2 5 4 3 1
    b = 1 2 4 5 3
    
    只要在数列 a 中重新定义 “大小” 关系
    让 4 < 3 ( 4 在 3 前面 ), 5 < 3 ( 5 在 3 前面 ) 即可
    
    定义一个数组 mmp, mmp[] = i 括号中放入数组 a[] b[]
    将 LIS 算法中的 i < j 都改成 mmp[ a[i] ] < mmp[ b[j] ] 就可以了

### [**【模板2】Common Subsequence**][2_Common Subsequence] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 2]

#include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e3+10;
    int dp[N][N];
    char a[N],b[N];
    
    int main()
    { 
    	while(~scanf("%s",a)) //很妙的读取方法
    	{ 
    		scanf("%s",b);
    		int n=strlen(a);
    		int m=strlen(b);
    		fill(dp[0],dp[0]+n*m,0);
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=m;j++)
    			{ 
    				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    				if(a[i-1]==b[j-1])
    					dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    			}
    		cout<<dp[n][m]<<endl;
    	}
    	return 0;
    }

**思路**  
大体思路一样，但注意接收的是字符串，因此判断条件的 `if(a[i] == b[j])` 要改成 `if(a[i-1] == b[j-1])`（因为从下标 0 开始接收字符）【并且本题的读取方法也很妙】

### [**最长公共子序列LCS**][2_Common Subsequence] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 3]

#include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e3+10;
    int dp[N][N];
    char a[N],b[N],c[N];
    
    int main()
    { 
    	scanf("%s %s",a,b);
    	int n=strlen(a);
    	int m=strlen(b);
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    		{ 
    			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    			if(a[i-1]==b[j-1])
    				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    		}
    	int z=0;
    	while(n!=0&&m!=0) //其中一方是 0就结束
    	{ 
    		if(a[n-1]==b[m-1]) { 
    			n--;m--;
    			c[z++]=a[n]; //b[n]
    		}
    		else if(dp[n][m-1]<dp[n-1][m]) n--;
    		else if(dp[n][m-1]>=dp[n][m-1]) m--;
    	}
    	for(int i=z-1;i>=0;i--)
    		cout<<c[i];
    	cout<<endl;
    	return 0;
    }

**思路**  
相比模板多了一个步骤：就是从末尾开始对比两串字符串，若字符相同就输出（任意一方）字符，否则对比哪一方的`DP`大（`DP` 越大代表  L C S LCS LCS 长度越长），向大的一方递减，直到其中一方的长度为 0 结束

### [**Advanced Fruits（根据LCS将两个词分解）**][2_Common Subsequence] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 4]

#include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e3+10;
    int dp[N][N];
    char a[N],b[N],c[N];
    
    int main()
    { 
    	while(~scanf(" %s",a))
    	{ 
    		scanf("%s",b);
    		int n=strlen(a);
    		int m=strlen(b);
    		memset(c,0,sizeof(c));
    		fill(dp[0],dp[0]+n*m,0);
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=m;j++)
    			{ 
    				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    				if(a[i-1]==b[j-1])
    					dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    			}
    		int z=0;
    		while(dp[n][m]) //一直到没有共同子序列的元素
    		{ 
    			if(a[n-1]==b[m-1])
    			{ 
    				n--;m--;
    				c[z++]=a[n]; //b[m]
    			}
    			else if(dp[n][m-1]<dp[n-1][m]) {  //可以调整
    				n--;
    				c[z++]=a[n];
    			}
    			else if(dp[n][m-1]>=dp[n][m-1]) {  //可以调整
    				m--;
    				c[z++]=b[m];
    			}
    		}
    		while(n!=0) c[z++]=a[--n];	//可以调整
    		while(m!=0) c[z++]=b[--m]; //可以调整
    		for(int i=z-1;i>=0;i--)
    			cout<<c[i];
    		cout<<endl;
    	}
    	return 0;
    }

**思路**  
题目意思：将两个字符串合并成一个字符串，两个字符串是合并后的字符串的子序列，要求并且完合并的字符串长度最短

既然合并完的长度最短，而合并完的长度最短为 `n + m - dp[n][m]`（ n n n 和  m m m分别是两个字符串的长度， d p dp dp 是两个的子序列），那么只有 d p dp dp最大才能保证整体最短，那么 L C S LCS LCS从末尾开始比较两串字符串，若字符相同就输出（任意一方）字符，否则对比哪一方的 `dp` 大（ `dp` 越大代表  L C S LCS LCS 长度越长），向大的一方递减，直到其中没有共同子序列的元素，最后还要把两个字符串插入所剩的元素分别输出

**注意**  
如果  w h i l e while while 循环用 `n!= 0 && m!= 0` 替换 `dp[n][m]` 有个歧义的地方，就是输出顺序问题，只能说译文的样例数据都保证  L C S LCS LCS 大于 0，要是举个例子：aaaaa 和 bbbbb（ L C S LCS LCS 等于 0），那就不能保证先输出 a 还是 b 了【其实用 `dp[n][m]` 也有相同的情况，若输出顺序有规定，则需要调整代码标记的地方】

### [**\[HAOI2010\]最长公共子序列**][HAOI2010] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 5]

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N=1e4+10;
    char a[N],b[N];
    ll dp[2][N],g[2][N];
    ll mod=1e8;
    
    int main()
    { 
    	scanf("%s",a);
    	scanf("%s",b);
    	int n=strlen(a)-1;
    	int m=strlen(b)-1;
    	for(int i=0;i<=m;i++) g[0][i]=1; // a的空字符串和 b的字符串的方案数定为 1 
    	g[1][0]=1; // a字符串和 b的空字符串的方案数定为 1 
    	int cnt=1;
    	for(int i=1;i<=n;i++)
    	{ 
    		for(int j=1;j<=m;j++)
    		{ 
    			g[cnt][j]=0; //重置为 0 
    			dp[cnt][j]=max(dp[cnt^1][j],dp[cnt][j-1]);
    			if(a[i-1]==b[j-1])
    				dp[cnt][j]=max(dp[cnt][j],dp[cnt^1][j-1]+1);
    			if(a[i-1]==b[j-1]&&dp[cnt][j]==dp[cnt^1][j-1]+1) // 一 
    				g[cnt][j]=g[cnt^1][j-1];
    			if(dp[cnt][j]==dp[cnt^1][j]) // 三四 
    				g[cnt][j]+=g[cnt^1][j];
    			if(dp[cnt][j]==dp[cnt][j-1]) // 二四 
    				g[cnt][j]+=g[cnt][j-1];
    			if(a[i-1]!=b[j-1]&&dp[cnt][j]==dp[cnt^1][j-1]) //四
    				g[cnt][j]-=g[cnt^1][j-1];
    			g[cnt][j]%=mod;
    		}
    		cnt^=1;
    	}
    	cout<<dp[cnt^1][m]<<endl;
    	cout<<g[cnt^1][m]<<endl;
    	return 0;
    }

**思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 6]  
**我的理解**  
什么情况下会  L C S LCS LCS 的种数会变化 ？  
只有在 `a[i]` 或 `b[j]` 至少有一个属于 `dp[i][j]` 时。因此我们可以列出下面所有的情况：  
一、`a[i]` 和 `b[j]` 都属于**所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)【 l c m ( i , j ) lcm(i, j) lcm(i,j) 即 `dp[i][j]`】  
二、`a[i]` 属于**所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)，`b[j]`并非属于**所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)  
三、`b[j]` 属于**所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)，`a[i]`并非属于**所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)

它们的伪代码如下：  
若 `a[i] = b[j]`，则 `dp[i][j] = dp[i - 1][j - 1] + 1`【对应一】

若 `dp[i][j] = dp[i][j - 1]`，则 `b[j]` 并非属于所有的  l c m ( i , j ) lcm(i, j) lcm(i,j)【对应二与其他】

若 `dp[i - 1][j] = dp[i][j]`，则 `a[i]` 并非属于所有的  l c m ( i , j ) lcm(i, j) lcm(i,j)【对应三与其他】

上面两种情况还有可能对应其他，也就是 `a[i]` 和 `b[j]` 都**不属于所有的**  l c m ( i , j ) lcm(i, j) lcm(i,j)，其它情况对应的伪代码是 `dp[i][j] = dp[i - 1][j - 1]`，它包含了上面两种合起来的其他情况，因此我们根据[容斥原理][Link 2]，要减去这些情况，因为只有对应一二三才使  L C S LCS LCS 的种数变化，其他情况不会

那么我们就可以列出其对应的表达式（`g[i][j]` 表示  l c m ( i , j ) lcm(i, j) lcm(i,j) 的种数）：

if (a[i] == b[j]) g[i][j] = g[i - 1][j - 1]	//对应一
    
    if (dp[i][j] == dp[i][j - 1]) g[i][j] += g[i][j - 1]	//对应二和其他
    
    if (dp[i][j] == dp[i - 1][j]) g[i][j] += g[i - 1][j]	//对应三和其他
    
    if (dp[i][j] == dp[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1]（容斥原理）

**注意**  
代码中 `cnt^1` 的 ^ 1 1 1是异或的意思，其使用方法如下

cnt = 0
    cnt ^= 1	//cnt = 0
    cnt ^= 1	//cnt = 1
    cnt ^= 1	//cnt = 0
    cnt ^= 1	//cnt = 1
    
    这样就构成了不断迭代 0 和 1，实现了滚动数组

[Link 1]: https://www.luogu.com.cn/problem/P1439
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/750fba44e1a447948bac39d5949c7c04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/dd5f095a37974caf98eb2586c5dd2da5.png
[2_Common Subsequence]: https://blog.csdn.net/lxt_Lucia/article/details/81209962
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/d1de63f14c974c99aba3a1ad57bd7eb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/0628f0a01ea1425d99203f446ba0bead.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/ef5a270f26854be2ae63ff6233e76b0b.png
[HAOI2010]: https://www.luogu.com.cn/problem/P2516
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/04f69eff3fa54e18931b161492bcbee8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/c494604f79354da99078583826ae78d8.png
[Link 2]: https://blog.csdn.net/CourserLi/article/details/109662920%29