精华内容
下载资源
问答
  • #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 <iostream>
    #include <string>
    using namespace std;
    #define MAXSIZE 100
    
    int max(int num1, int num2)
    {
        return num1>num2?num1:num2;
    }
    
    int main()
    {
        char strA[MAXSIZE];
        char strB[MAXSIZE];
        int maxLen[MAXSIZE][MAXSIZE] = {0};
        int i;
        int j;
        cin >> strA;
        cin >> strB;
        int lenA = strlen(strA);
        int lenB = strlen(strB);
        for (i=1; i<=lenA; i++)
            for (j=1; j<=lenB; j++)
            {
                if (strA[i-1] == strB[j-1])
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                else
                    maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]);
            }
        cout << maxLen[lenA][lenB] << endl;
        return 0;
    }

     

    转载于:https://www.cnblogs.com/jlbs/p/6486195.html

    展开全文
  • 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;...

    # include<stdio.h>
    # include<stdlib.h>
    # include<iostream.h>
    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<m;i++)
      for(j=0;j<n;j++)
       X.A[i][j]=0;
     for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
      {
       if(A[i]==B[j])
       {
        X.A[i][j]=X.A[i-1][j-1]+1;
        Y.A[i][j]=2;
       }
       else if(X.A[i-1][j]>=X.A[i][j-1])
       {
        X.A[i][j]=X.A[i-1][j];
        Y.A[i][j]=1;
       }
       else
       {
        X.A[i][j]=X.A[i][j-1];
        Y.A[i][j]=0;
       }
      }
      
    }
    void LCS(MA &Y,int m,int n,char A[])
    {
     if(m==0||n==0)
     ;
     else
     if(Y.A[m][n]==2)
     {
      
      LCS(Y,m-1,n-1,A);
      printf("%c",A[m]);
     }
     else if(Y.A[m][n]==1)
      LCS(Y,m-1,n,A);
     else
      LCS(Y,m,n-1,A);

    }
    int main()
    {
     char A[256],B[256];
     int i;
     int m,n;
     cout<<"m:"<<endl;
     cin>>m;
     for(i=1;i<=m;i++)
      cin>>A[i];
     cout<<"n:"<<endl;
     cin>>n;
     for(i=1;i<=n;i++)
      cin>>B[i];
     MA X,Y;

     LCS_LENGTH(m,n,A,B,X,Y);
     LCS(Y,m,n,A);
     return 0;
    }

     

    展开全文
  • LCS最长公共子序列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

    思路

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

    代码

    #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

    思路

    动态规划
    str1[i1]==str2[j1]str1[i-1] == str2[j-1]时,dp[i][j]=dp[i1][j1]+1dp[i][j] = dp[i - 1][j - 1] + 1
    只是当str1[i1]=str2[j1]str1[i-1] != str2[j-1]时,dp[i][j]=0dp[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;
    	}
    };
    
    展开全文
  • 最长公共子序列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;
    } 
    
    展开全文
  • 最长公共子序列长度(LCS问题) #include <iostream> #include <string.h> #include <algorithm> using namespace std; int lcs(string str1,string str2){ int len1=str1.size(),len2=str2....
  • 最长公共子序列代码。。有很详细的注释,C++的,能够正常运行。
  • 程序分为两个部分LCSLength()函数寻找最长公共子序列,LCS()函数打印最长公共子序列 具体代码如下 #include<iostream> #include<iomanip> using namespace std; int main() { int c[7][7],b[7][7]; ...
  • 最长公共子序列C++代码) #include using namespace std; void LCSLength(int m,int n,char *x,char *y,int c[][100] ,int b[][100]) { int i,j; c[0][0]=0; for(i=1;i;i++)c[i][0]=0; for(j=1;j;j++)c[0]...
  • 看了邓老师的数据结构,讲动态规划,以求最长公共子序列作为例子。下面是我学习总结,作为记录存档。 第一种方法是通过递归实现。思路如下,两字符串长度长度分别为 a,b,比较他们的末位字符,这里是有三种情况 若...
  • 南邮算法实验之动态规划法实验,解决了基本最长公共子序列问题以及相关拓展思考题,代码注释详尽,简单易懂
  • 主要给大家介绍了如何利用C++实现最长公共子序列与最长公共子串,文章一开始就给大家简单的介绍了什么是子序列,子串应该比较好理解就不用多介绍了,人后通过算法及示例代码详细介绍了C++实现的方法,有需要的朋友们...
  • 最长公共子序列核心代码(clodeblocks运行通过)
  • 时间复杂度为O(nm)O(nm)O(nm)(n、mn、mn、m分别为两个字符串的长度): #define _CRT_SECURE_NO_WARNINGS #include <cstring> #include <iostream> #include <algorithm>...using namespace std;...
  • # include # include const int ..."最长长度为:" c [ len1 ] [ len2 ] endl ; Print ( len1 , len2 ) ; return 0 ; } ABCBADB BCBAAC 长度:4, BCBA
  • //这里我只用这一行代码,只用了一个变量,自然是无法保存,因为到下轮开始就会更新了,所以应该是先保存下来,等到dp[j]更新过后,再更新到pre temp=dp[j]; if(text1[i-1]==text2[j-1]) dp[j]=pre+1; else dp[j]=...
  • 输出一个最长公共子序列并不难(网上很多相关代码),难点在于输出所有的最长公共子序列,因为 LCS 通常不唯一。 我们需要在动态规划表上进行回溯 —— 从c[m][n],即右下角的格子,开始进行判断: 如...
  • c++语言写的最长公共子序列问题,比较经典的动态规划问题。能完美运行,输入2个字符串序列之后就能得出最长公共子序列
  • (1)确定合适的数据结构 采用二维数组c[][]来记录最长公共子序列的长度,二维数组b[][]来记录最长公共子序列的长度的来源,以便算法结束时倒推求解得到该最长公共子序列。 (2)初始化 输入两个字符串s1、s2,初始...
  • 最长公共子串前言最长公共子序列介绍实现原理1.暴力算法2.动态规划代码展示时间复杂度分析 前言 这篇博客是为了方便我的算法设计与分析课程的讲解的,是作业驱动型,所以不会太适合用来学习 最长公共子序列 介绍 ...
  • C++版解决最长公共子序列问题最长公共子序列问题问题描述思路方法 最长公共子序列问题 问题描述 最近适逢秋招,于是刷了一些题。腾讯的某道题完全没有思路,看到的网上解析遂发觉了这么个经典的“模板问题”。 输入...
  • 最长公共子序列长度 C++ 动规入门暴力递归:动规: 问题描述:给定两个字符串A和B,求一个字符串,使得该字符串为A和B的最长公共子序列,求该字符串的长度 样例输入: sadstory adminsorry 样例输出: 6 样例解释: ...
  • 算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
  • 若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,...给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子
  • 最长公共子序列(c++实现)

    千次阅读 2018-10-31 16:42:27
    问题:给定两个长度分别为m,n的字符串,求他们的最长公共子序列,要求时间复杂度为O(m+n)。 解决思路: 声明两个二维数组,cArray[i][j]代表在此位置时两个字符串已经存在了多少公共字符,sArray[i][j]用于回溯...
  • 使用一个二维数组arr[n+1][m+1]来记录每种情况下最长公共子序列的长度。 初始状态:字符串a空元素,字符串b空元素。这样的情况就填0.也就是二维数组首行首列全为0. 假设: a{a,b,c,d} b{b,c,a,d} 行 i 是字符...
  • 最长公共子序列C++实现代码

    千次阅读 2011-09-03 19:09:54
    这里需要注意的是c[i][j]对应的是以data1[i-1],data2[j-1]结束的子串的最长公共子序列。 问题的递归式写成: 回溯输出最长公共子序列过程:   算法分析: 由于每次调用至少向上或向左...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,840
精华内容 2,336
关键字:

最长公共子序列c++代码

c++ 订阅