精华内容
下载资源
问答
  • 最长公共子序列C++

    2020-06-10 19:37:42
    最长公共子序列问题描述最长公共子序列问题分析代码 问题描述 先来了解一下字串和子序列,一个串的子串是指该串的一个连续的局部。如果不要求连续,则可称为它的子序列。 比如对串: “abcdefg” 而言,“ab”,“abd...

    问题描述

    先来了解一下字串和子序列,一个串的子串是指该串的一个连续的局部。如果不要求连续,则可称为它的子序列。
    比如对串: “abcdefg” 而言,“ab”,“abd”,“bdef” 等都是它的子序列。
    特别地,一个串本身,以及空串也是它的子序列。

    最长公共子序列

    给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。
    例如:abcfbc与abfcab的最长公共子序列是abcb

    问题分析

    输入两个串s1,s2,设MaxLen(i, j)表示:s1的左边i个字符形成的子串,与s2左边j个字符形成的子串的最长公共子序列的长度。(i,j从0开始算)
    MaxLen(i, j)就是本题的“状态”
    假定len1 = strlen(s1), len2 = strlen(s2)。那么题目就是要求 MaxLen(len1, len2)
    显然:
    MaxLen(n, 0) = 0 (n = 0~len1)
    MaxLen(0, n) = 0 (n = 0~len2)
    递推公式:
    if(s1[i-1] == s2[j-1])
    MaxLen(i, j) = MaxLen(i-1, j-1) + 1;
    else
    MaxLen(i, j) = Max(MaxLen(i, j-1), MaxLen(i-1, j));
    s1[i-1] != s2[j-1]时,MaxLen(i, j)不会比MaxLen(i-1, j)和MaxLen(i, j-1)两者之中任何一个小,也不会比任何一个大。

    代码

    #include<iostream>
    #include<cstring>
    using namespace std;
    //两个原串 
    char s1[1000], s2[1000];
    //存放s1的左边i个字符形成的子串,与s2左边j个字符形成的子串的最长公共子序列的长度 
    int maxLen[1000][1000];
    int main() {
    	while(cin >> s1 >> s2) {
    		int len1 = strlen(s1);
    		int len2 = strlen(s2);
    		//先处理MaxLen(n, 0)和MaxLen(0, n)的情况  
    		for(int i = 0; i <= len1; i++)
    			maxLen[i][0] = 0;
    		for(int j = 0; j <= len2; j++)
    			maxLen[0][j] = 0;
    			
    		//遍历两个原串	
    		for(int i = 1; i <= len1; i++) {
    			for(int j = 1; j <= len2; j++) {
    				if(s1[i-1] == s2[j-1])//此处的s1、s2的下表从0开始 s1[i-1]代表s1的第i个字符 
    					maxLen[i][j] = maxLen[i-1][j-1] + 1;//此处的i-1、j-1与上面意义不同 
    				else 
    					maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]);
    			}
    		}
    		cout << maxLen[len1][len2] << endl;
    	}
    	return 0;
    } 
    
    展开全文
  • 最长公共子序列c++

    2009-01-04 18:04:25
    c++实现最长公共子序列,实验课程作业,绝对可以运行。
  • 最长公共子序列c++实现

    千次阅读 2019-08-11 19:52:28
    最长公共子序列 给定两个字符串S1和S2,求两个字符串的最长公共子序列的长度。 输入样例 ABCD AEBD 输出样例 3 解释 S1和S2的最长公共子序列为ABD,长度为3 思路 动态规划 LCS(m,n)LCS(m ,n)LCS(m,n)表示S1[0...m]S1...

    最长公共子序列

    给定两个字符串S1和S2,求两个字符串的最长公共子序列的长度。
    输入样例
    ABCD
    AEBD
    输出样例
    3
    解释
    S1和S2的最长公共子序列为ABD,长度为3

    思路

    动态规划
    L C S ( m , n ) LCS(m ,n) LCS(m,n)表示 S 1 [ 0... m ] S1[0...m] S1[0...m] S 2 [ 0... n ] S2[0...n] S2[0...n]的最长公共子序列的长度
    S 1 [ m ] = = S 2 [ n ] : L C S ( m , n ) = 1 + L C S ( m − 1 , n − 1 ) S1[m] == S2[n]: LCS(m, n) = 1 + LCS(m - 1, n - 1) S1[m]==S2[n]:LCS(m,n)=1+LCS(m1,n1)
    S 1 [ m ] ! = S 2 [ n ] : L C S ( m , n ) = m a x ( L C S ( m − 1 , n ) , L C S ( m , n − 1 ) ) S1[m] != S2[n]: LCS(m, n) = max(LCS(m - 1, n), LCS(m, n - 1)) S1[m]!=S2[n]:LCS(m,n)=max(LCS(m1,n),LCS(m,n1))

    代码

    #include <iostream>
    #include <vector>
    #include <set>
    using namespace std;
    
    class Solution{
    public:
        int lengthOflongestCommonSequence(string& str1, string& str2){
            int m = str1.length(), n = str2.length();
            if(m == 0 || n == 0)
                return 0;
            dp = vector<vector<int> >(m+1, vector<int>(n+1, 0));
            for(int i = 1; i < m+1; ++i){
                for(int j = 1; j < n+1; ++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]);
                }
            }
            return dp[m][n];
        }
        // 找出所有的LCS的序列
        // 这里形参lcs_str不可以为引用,这里需要每次调用lcs_str都重新生成一个对象
        void PrintAllLCS(string& str1, string& str2, int i, int j, string lcs_str){
            while(i > 0 && j > 0){
                if(str1[i-1] == str2[j-1]){
                    lcs_str = str1[i-1] + lcs_str;
                    --i;
                    --j;
                }
                else{
                    if(dp[i-1][j] > dp[i][j-1])  //向左走
                        --i;
                    else if(dp[i-1][j] < dp[i][j-1])  //向上走
                        --j;
                    //此时向上向右均为LCS的元素
                    else{
                        PrintAllLCS(str1, str2, i-1, j, lcs_str);
                        PrintAllLCS(str1, str2, i, j-1, lcs_str);
                        return;
                    }
                }
            }
            all_lcs.insert(lcs_str);
        }
        vector<vector<int>> dp;
        set<string> all_lcs;
    };
    
    int main()
    {
        string s1 = "abcfbc";
        string s2 = "abfcab";
        Solution fir;
        string lcs_str;
        int res = fir.lengthOflongestCommonSequence(s1, s2);
        cout << res << endl;
        fir.PrintAllLCS(s1, s2, s1.length(), s2.length(), lcs_str);
        set<string>::iterator iter = fir.all_lcs.begin();
    	while (iter != fir.all_lcs.end()) {
    		cout << *iter++ << endl;
    	}
        return 0;
    }
    /*
    4
    abcb
    abfb
    abfc
    */
    

    最长公共子串

    求两个字符串的最长公共子串,要求子串连续
    输入例子:
    bab
    caba
    输出例子:
    2

    思路

    动态规划
    s t r 1 [ i − 1 ] = = s t r 2 [ j − 1 ] str1[i-1] == str2[j-1] str1[i1]==str2[j1]时, d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j]=dp[i1][j1]+1
    只是当 s t r 1 [ i − 1 ] ! = s t r 2 [ j − 1 ] str1[i-1] != str2[j-1] str1[i1]=str2[j1]时, d p [ i ] [ j ] = 0 dp[i][j] = 0 dp[i][j]=0

    代码

    class Solution {
    public:
    	int lengthOflongestCommonSubstring(string& str1, string& str2){
        	int m = str1.size(), n = str2.size();
        	int res = 0;
        	vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        	for(int i = 1; i <= m; ++i){
            	for(int j = 1; j <= n; ++j){
                	if(str1[i-1] == str2[j-1])
                    	dp[i][j] = dp[i-1][j-1] + 1;
                	else
                    	dp[i][j] = 0;
                	if(res < dp[i][j])
                    	res = dp[i][j];
            	}
        	}
        	return res;
    	}
    };
    
    展开全文
  • LCS最长公共子序列c++的代码。动态规划思想
  • 程序分为两个部分LCSLength()函数寻找最长公共子序列,LCS()函数打印最长公共子序列 具体代码如下 #include<iostream> #include<iomanip> using namespace std; int main() { int c[7][7],b[7][7]; ...

    程序分为两个部分LCSLength()函数寻找最长公共子序列,LCS()函数打印最长公共子序列

    具体代码如下

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int main()
    {
    	int c[7][7],b[7][7];
    	char x[7],y[7];
    	int *p[7],*q[7];
    	void LCSLength(int m,int n,char *x,char *y,int **c,int **b);
    
    	cout<<"请输入第一个数组:"<<endl;
    	for(int k=0;k<7;k++)
    	{	
    		cin>>x[k];
    		p[k]=c[k];
    		q[k]=b[k];
    		
    	}
    	cout<<"请输入第二个数组:"<<endl;
    	for(int l=0;l<7;l++)
    	{
    		cin>>y[l];
    	}
    	LCSLength(7,7,x,y,p,q);
    	return 0;
    }
    
    
    void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
    {
    	int i,j;
    	int *z[7];
    	for(i=0;i<m;i++)
    	{
    		c[i][0]=0;
    		b[i][0]=0;
    	}
    	for(i=0;i<n;i++)
    	{
    		c[0][i]=0;
    		b[0][i]=0;
    	}
    	for(i=1;i<m;i++)
    	{
    		for(j=1;j<n;j++)
    		{	
                if(x[i]==y[j])
    			{
    				c[i][j]=c[i-1][j-1]+1;
    				b[i][j]=1;
    			}
    			else if(c[i-1][j]>=c[i][j-1])
    			{
    				c[i][j]=c[i-1][j];
    				b[i][j]=2;
    			}
    			else //c[i-1][j]<c[i][j-1]
    			{
    				c[i][j]=c[i][j-1];
    				b[i][j]=3;
    			}
    		}
    		cout<<endl;
    	}
    
    	for(int o=0;o<7;o++)
    	{
    		z[o]=b[o];
    	}
    	LCS(7,7,x,z);
    }
    
    void LCS(int i,int j,char *x,int **b)
    {
    
    	cout<<"最长公共子序列为:"<<endl;
    	for(int k=0;k<i;k++)
    	{
    		for(int l=0;l<j;l++)
    		{
    			if(b[k][l]==1)
    			{
    				cout<<x[k];
    			}
    		
    		}
    	}
    	cout<<endl;
    }

    运行结果为:

    其输入数组第一个值为数组长度,后面为要求的序列

    展开全文
  • 看了邓老师的数据结构,讲动态规划,以求最长公共子序列作为例子。下面是我学习总结,作为记录存档。 第一种方法是通过递归实现。思路如下,两字符串长度长度分别为 a,b,比较他们的末位字符,这里是有三种情况 若...

    邓俊辉版数据结构,动态规划求解最长公共子序列学习总结。
    第一种方法是通过递归实现。思路如下,两字符串长度长度分别为 a,b,比较他们的末位字符,这里是有三种情况

    1. 若有一方长度为零,则返回“”,这是递归方程的递归基。
    2. 若两字符串的末位字符相同,去掉末尾字符,返回规模递减的问题f(a-1,b-1)。这里是“减而治之”策略。
    3. 若两字符串末位字符不同,则有两种情况通过比较(a-1,b) 和(a,b-1)长度的字符串的最长公共子序列的长度,像长度较大的方向继续进行递归,返回f(a-1,b)或f(a,b-1),这里用的是“分而治之”策略。

    实现代码如下

    
    
    #include <iostream>
    using namespace std;
    string substring = ""; 
    string lcs(string s1,string s2);
    int main(){
        string s1, s2;
        cout << "please enter the first string\n";
        cin >> s1;
        cout << "please enter the second string\n";
        cin >> s2;
        cout<<"the longest conmmon subsequence is "<<lcs(s1, s2);
    }
    string lcs(string s1,string s2){   
        int a,b;
        a = s1.length()-1;
        b = s2.length()-1;
        if(a==-1||b==-1){
            //substring += "";
            //reverse(substring.begin(),substring.end());
            return "";
        }
        else if(s1[a]==s2[b]){
            //substring += s1[a];
            char m = s1[a];
            s1 = s1.substr(0, a);
            s2 = s2.substr(0, b);
            return lcs(s1,s2)+m;
        }
        else{
            string s11 = s1.substr(0, a);
            string s22 = s2.substr(0, b);
            int l1 = lcs(s11, s2).length();
            int l2 = lcs(s1, s22).length();
            if(l1>l2){
                s1 = s11;
                return lcs(s1,s2);
            }
            else{
                s2 = s22;
                return lcs(s1,s2);
            }
        }
    }
    
    

    这种递归的方法由于多次重复计算,时间复杂度在最坏情况下达到O(2^n).

    第二种方法是用迭代,通过动态规划用表来存储较短的字符串的公共子序列长度,就避免的了大量重复计算,方法是上面递归方法的逆向执行,比如1313和
    431254的最长公共子序列,列表
    0 0 0 0 0 0 0
    0 0 0 1 1 1 1
    0 0 1 1 1 1 1
    0 0 1 2 2 2 2
    0 0 1 2 2 2 2
    通过循环遍历长宽为a+1,b+1的列表,第一行和第一列初始化为0,相同就填入左上加一,不同就填入左边或上面格子中较大的那个数,填满表格,表格的最右下角即为所求最长公共子序列的长度。
    下面是一开始写的,可以得到正确长度但输出的最长公共子序列有误。

    #include <iostream>
    using namespace std;
    string substring = "";
    int maxelement = 0;
    int max(int *p, int a, int b);
    string lcs(string s1,string s2);
    int main(){
        string s1, s2;
        cout << "please enter the first string\n";
        cin >> s1;
        cout << "please enter the second string\n";
        cin >> s2;
        string s = lcs(s1, s2);
        cout<<"the longest conmmon subsequence is "<<s;
    }
    string lcs(string s1,string s2){
        int a = s1.length();
        int b = s2.length();
        int list[a+1][b + 1];
        for (int m = 0; m < a + 1;m++){
            for (int n = 0; n < b + 1;n++){
                list[m][n] = 0;
            }
        }
        for (int i = 1; i < a + 1; i++){
            for (int j = 1; j < b + 1; j++){
                if (s1[i-1] == s2[j-1]){
                    list[i][j] = list[i - 1][j - 1] + 1;
                    if (list[i][j] >= max(list[0],a+1,b+1)){
                        //cout << "ii" << i << "jj" << j;
                        substring += s1[i - 1];
                    }
                }
                else{
                    list[i][j] = (list[i - 1][j] > list[i][j - 1]) ? list[i - 1][j] : list[i][j - 1];
                }
            }
        }
        for (int m = 0; m < a + 1;m++){
            for (int n = 0; n < b + 1;n++){
                cout<<" "<<list[m][n];
            }
            cout << "\n";
        }
        return substring;
    }
    int max(int *p,int a,int b){
        int max = 0;
        for (int i = 0; i < a;i++){
            for (int j = 0; j<b;j++){
                if(*( p+i*b+j)>max){
                    max = *(p + i * b + j);
                }
            }
        }
        if(max > maxelement){
            maxelement = max;
        }
        else if(max==maxelement){
            max = max + 1;
        }
        return max;
    }
    

    经过手动测试,以上程序不能正确输出最长公共子序列的原因在于它通过找到记录列表中令每个最大值第一次出现的那个字符,并加入substring。但像这样判断是不完善的,第一次匹配到的元素是不会随着更大更长的公共子序列的出现而替换的。因此通过一个标志数组来记录搜索进行的方向,然后再由得到最长公共子序列的那一条路径求得这两个字符串的最长公共子序列。

    实现代码

    #include <iostream>
    using namespace std;
    string substring = "";
    int symbol[100][100];
    void lcs(string s1,string s2);
    string show(int i, int j, string x);
    int main(){
        string s1, s2;
        cout << "please enter the first string\n";
        cin >> s1;
        cout << "please enter the second string\n";
        cin >> s2;
        lcs(s1, s2);
        show(s1.length(), s2.length(), s1);
        cout<<"the longest conmmon subsequence is "<<substring;
    }
    void lcs(string s1,string s2){
        int a = s1.length();
        int b = s2.length();
        int list[a+1][b + 1];
        for (int m = 0; m < a + 1;m++){
            for (int n = 0; n < b + 1;n++){
                list[m][n] = 0;
            }
        }
        for (int i = 1; i < a + 1; i++){
            for (int j = 1; j < b + 1; j++){
                if (s1[i-1] == s2[j-1]){
                    list[i][j] = list[i - 1][j - 1] + 1;
                    symbol[i][j] = 0;
                            }
                else if(list[i - 1][j] > list[i][j - 1]){
                    list[i][j] = list[i - 1][j];
                    symbol[i][j] = 1;
                }
                else{
                    list[i][j] = list[i][j - 1];
                    symbol[i][j] = 2;
                }                
            }
        }
        for (int m = 0; m < a + 1;m++){
            for (int n = 0; n < b + 1;n++){
                cout<<" "<<symbol[m][n];
            }
            cout << "\n";
        }
    }
    string show(int i,int j,string x)
    {
        if(i==0||j==0)
            return substring;
        if(symbol[i][j]==0)
        {
            show(i-1,j-1,x);
            substring+=x[i-1];
            return substring;
        }
        else if(symbol[i][j]==1){
            show(i-1,j,x);
            return substring;
        }
        else{
            show(i,j-1,x);
            return substring;
        }
    }
    

    此方法的时间复杂度是o(m+n+m * n),包括求字符的m + n和求字符串长度的m * n。

    展开全文
  • #include <iostream> #include <string> using namespace std; #define MAXSIZE 100 int max(int num1, int num2) { return num1>num2?num1:num2; } int main() ... char...
  • # include # include const int ..."最长长度为:" c [ len1 ] [ len2 ] endl ; Print ( len1 , len2 ) ; return 0 ; } ABCBADB BCBAAC 长度:4, BCBA
  • 这个应该是动态规划入门题。很多讲动态规划的都是用这道题去讲。 class Solution { public: int longestCommonSubsequence(string text1, string text2) { vector<int> p(text2.size()+1,0);...
  • 最长公共子串前言最长公共子序列介绍实现原理1.暴力算法2.动态规划代码展示时间复杂度分析 前言 这篇博客是为了方便我的算法设计与分析课程的讲解的,是作业驱动型,所以不会太适合用来学习 最长公共子序列 介绍 ...
  • #include <iostream> #include <string.h> using namespace std; #define MAXLEN 100 void LCSlength(char *x,char *y,int m,int n,int c[][MAXLEN],int b[][MAXLEN]) { ... c[0][i]=0
  • LCS最长公共子序列C++代码实现

    千次阅读 2014-01-17 08:10:52
    # include # include # include typedef struct matrix {  int A[200][200]; }MA; void LCS_LENGTH(int m,int n,char A[],char B[],MA &X,MA &Y) {  int i,j;  for(i=0;i  for(j=0;...
  • 一、给定两个字符串S1和S2,求两个字符串的最长公共子序列的长度。 输入样例 ABCD AEBD 输出样例 3 解释 S1和S2的最长公共子序列为ABD,长度为3 思路 动态规划 LCS(m,n)表示S1[0…m]和S2[0…n]的最长公共子序列的...
  • 主要给大家介绍了如何利用C++实现最长公共子序列与最长公共子串,文章一开始就给大家简单的介绍了什么是子序列,子串应该比较好理解就不用多介绍了,人后通过算法及示例代码详细介绍了C++实现的方法,有需要的朋友们...
  • 最长公共子序列.doc

    2021-08-06 17:45:11
    最长公共子序列C++源码
  • 问题描述:给定两个序列,例如 X = “ABCBDAB”、Y = “BDCABA”,求它们的最长公共子序列的长度。 下面是求解时的动态规划表,可以看出 X 和 Y 的最长公共子序列的长度为4: 输出一个最长公共子序列并不难(网上很...
  • c++语言写的最长公共子序列问题,比较经典的动态规划问题。能完美运行,输入2个字符串序列之后就能得出最长公共子序列
  • 动态规划篇——最长公共子序列(c++)

    千次阅读 多人点赞 2019-06-11 17:28:51
    引言:最长公共子序列属于动态规划的基础篇,由字符串的最长公共最序列可以引出很多的问题。 最长子序列详细讲解以及练习题目 需要详细讲解教程的可以观看上面链接的文章,以下是自己做的简单的概括。 一、何为...
  • C++版解决最长公共子序列问题最长公共子序列问题问题描述思路方法 最长公共子序列问题 问题描述 最近适逢秋招,于是刷了一些题。腾讯的某道题完全没有思路,看到的网上解析遂发觉了这么个经典的“模板问题”。 输入...
  • 这里有最长公共子序列问题的各种实现!希望对大家会有帮助
  • 最长公共子序列

    2012-10-31 15:18:50
    最长公共子序列C++,需输入两个序列的长度和内容
  • 最长公共子序列长度 C++ 动规入门暴力递归:动规: 问题描述:给定两个字符串A和B,求一个字符串,使得该字符串为A和B的最长公共子序列,求该字符串的长度 样例输入: sadstory adminsorry 样例输出: 6 样例解释: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,784
精华内容 3,113
关键字:

最长公共子序列c++

c++ 订阅