最长公共子序列

以你之姓@ 2023-02-14 02:38 3阅读 0赞

问题描述：  
寻找两个字符串a,b中最长公共的子序列。  
例如：a,b,c,h与 b,d,h  
显然时b,h  
虽然肉眼判断十分容易看出来，但是要用计算机的语言进行求解还是有一点难度，或者说当问题规模变大时，人一点点来判断就十分难来。。（计算机的最强的地方就在于计算。。）  
补充：计算机计算能力,一般 1.8G左右 也就是1\*10^9，在时间复杂度超过此数时就得想办法优化算法了。

问题类型：  
动态规划

分析步骤：  
（1）进行比较记录比较的情况（使用二维数组进行记录）  
（2）进行递推实现输出（分三种情况）

**递推**

1.  字符相同为情况一，并且记录长度的数组加一
2.  不同时进行两种情况讨论，选择其长度较长的（理解为选择更优的子问题）  
    ![在这里插入图片描述][20200531153442782.png_pic_center]  
    **实现形式:**  
    1.数据结构：类，方便记录访问数据

2.二维数组进行记录长度和分类情况

3.递推：三种情况进行递归（确定截止条件 ）

4.确定输出形式：最优长度以及序列（逆序或者正的）

代码：

```cpp
    #include<iostream>
    using namespace std;
    int I=0;
    class F {
    	public :
    		F(char *A,char *B,int n,int m) { //字符A，B：以及其长度
    			a=A;
    			b=B;
    			n1=n;
    			m1=m;
    		}
    		int record() {//记录最长长度
    			for(int i=0; i<=n1; i++)
    				for(int j=0; j<=m1; j++)
    					c[i][j]=0;
    			for(int i=1; i<=n1; i++)
    				for(int j=1; j<=m1; j++) {
    					if(a[i-1]==b[j-1]) {
    						c[i][j]=c[i-1][j-1]+1;
    						s[i][j]=1;
    					} else if(c[i-1][j]>=c[i][j-1]) {
    						/*比较子问题 ，难点理解：子问题i-1长度
    						的 a 与 j 长度的b 以及 	i长度的a 和j-1 的长度的b比较，记录长的 */
    
    						c[i][j]=c[i-1][j];
    						s[i][j]=2;
    					} else {
    						c[i][j]=c[i][j-1];
    						s[i][j]=3;
    					}
    				}
    			return c[n1][m1];
    		}
    		void print(int i,int j,char *XX) {//数组记录情况，逆序输出
    
    			if(i==0||j==0)return ;//地推结束
    			else	if(s[i][j]==1) {
    				XX[I]=a[i-1];
    				I++;
    				print(i-1,j-1,XX);
    			} else if(s[i][j]==2) {
    				print(i-1,j,XX);
    			} else {
    				print(i,j-1,XX);
    			}
    
    
    		}
    	private:
    		int s[10][10],n1,m1,c[10][10];
    		char *a,*b;
    };
    int main() {
    	char AA[5]= {'v','f','g','h','l'},BB[6]= {'f','m','n','h','j'};
    	char D[10];
    	int N=5,M=6;
    	F f(AA,BB,5,6);
    	f.record();
    
    	cout<<"长度为："<<f.record()<<" 序列为:";
    	f.print(5,6,D);
    
    	for(int i=I; i>=0; i--) {
    		cout<<D[i];
    	}
    	return 0;
    }

[20200531153442782.png_pic_center]: https://img-blog.csdnimg.cn/20200531153442782.png#pic_center