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

    2017-12-03 03:47:15
    动态规划——最长公共子序列长度

    花了一两个小时才清楚了最长公共自序列..咸鱼加油

    废话不多说,直接解题报告吧..


    【简要描述】

    给出任意俩字符串(长度小于1000)求出最长公共自序列的长度

    【分析与算法设计】

    最长公共子序列是动态规划中的其中一个经典问题。

    唔..最简单的..首先输入两串字符应该不用详细介绍;重点解决如何计算最长公共子序列,而思路最先想到的是可以设计一个maxLen(i,j),来表示本题的状态:字符串sz1左边i个字符形成的子串与sz2左边的j个字符形成的子串的最长公共子序列长度。

    假定sz1的字符串长度为length1=strlen(sz1),sz2的字符串长度length2=strlen(sz2),那么maxLen(length1,length2)即为题目思路要求。而maxLen(n,0)(n属于0~length1)和maxLen(0,n)(n属于0~length2)为边界条件。

    开始分析问题情况。第一种:sz1的i-1项与sz2的j-1项相等,则maxLen(i-j)=maxLen(i-1,j-1)+1,即公共子序列长度增加一个单位。第二种:不相等,则需求出在此两项之前的两端子序列的公共自序列的长度,即maxLen(i,j-1)和maxLen(i-1,j)两个中最大的那一个。(本段为递推的内容)

    由这两个字符串中各项的比较,可以用列表来计算,而列表可用二维数组来表示。(如图..不要在意细节)

    i,jjjjj
    i    
    i    
    i    

    若俩字符串长度分别为i和j,则该列表长度为i+1和j+1,坐标(a,b)表示sz1前a个字符与sz2前b个字符最长公共自序列。(递推的内容演绎,咸鱼式表达)

    反正递推完就能得结果了_(:3<L)_XIANYU

    时间复杂度:O(nm) n,m分别为俩字符串长度

    【代码呈现】

    啥也别说了,直接代码吧...

    #include<iostream>
    #include<cstring>
    using namespace std;
    char sz1[1000];
    char sz2[1000];
    int maxLen[1000][1000];
    int max(int a,int b) {
    	return a>b?a:b;
    }
    int main() {
    	while(cin>>sz1>>sz2) {
    		int length1=strlen(sz1);     //字符串1长度
    		int length2=strlen(sz2);     //字符串2长度
    		int i,j;
    		for(i=0;i<=length1;i++)      //对二维数组边界初始化
    			maxLen[i][0]=0;
    		for(j=0;j<=length2;j++)
    			maxLen[0][j]=0;
    		for(i=1;i<=length1;i++) {               //递推一排一排比较...              
    			for(j=1;j<=length2;j++) {
    				if(sz1[i-1]==sz2[j-1])     //两字符相等情况
    					maxLen[i][j]=maxLen[i-1][j-1]+1;
    				else        //不相等情况...                                          
    					maxLen[i][j]=max(maxLen[i][j-1],maxLen[i-1][j]);
    			}
    		}
    		cout<<maxLen[length1][length2]<<endl;
    	}
    	return 0;
    }

    【题源】POJ1458


    好了,咸鱼的第一次结题报告到此结束...估计过一段时间来自己都看不懂...那就隔一段时间修改一次吧...



    展开全文
  • 最长公共子序列长度

    千次阅读 2019-03-15 21:06:37
    求两个字符串的公共子序列1.求最长公共子序列(子序列可以不连续)2.最长连续子串 1.求最长公共子序列(子...例如,a串abbcd,b串abcd,dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度,值为2。...

    求两个字符串的公共子序列


    1.求最长公共子序列(子序列可以不连续)

    这是一道动态规划题,设二维数组dp[i][j],dp[i][j]表示a串前i个字符(包括第i个)与b串前j个字符(包括第j个)所有的公共子序列的最长长度。
    例如,a串abbcd,b串abcd,dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度,值为2。a串中的ab与b串中的ab一致,长度为2。
    求dp数组的方法为:
    dp[i][j] = 0 , i == 0 || j == 0
    dp[i][j] = dp[i-1][j-1] +1 , a[i] = b[j]
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]) , a[i] !=b[j]

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main(){
        string a,b;
        cin>>a>>b;
        int alen = a.size();
        int blen = b.size();
        int dp[100][100];
        for(int i=0;i<alen+1;i++) dp[i][0]=0;   //若i==0或j==0
        for(int j=0;j<alen+1;j++) dp[0][j]=0;  //dp[i][j] = 0
        for(int i=1;i<alen+1;i++){
            for(int j=1;j<blen+1;j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                	dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }
                cout<<dp[i][j]<<"  ";   //输出当前dp矩阵
            }
        }
        cout<< dp[alem][blen];       //dp[alem][blen]即为当前两个串的最长公共子序列长度
    }
    
    

    2.最长连续子串

    求最长连续子串比不连续的简单了一些,只需删除上边代码里的else部分即可,这里的dp[i][j]可以理解为以a的第i个字符与b的第j个字符为结尾的最长公共子串的长度,由此可得a[i] != b[j]时,dp[i][j] = 0

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main(){
        string a,b;
        cin>>a>>b;
        int alen = a.size();
        int blen = b.size();
        int dp[100][100];
        int Max=0;
        for(int i=0;i<alen+1;i++) dp[i][0]=0;
        for(int j=0;j<alen+1;j++) dp[0][j]=0;
        for(int i=1;i<alen+1;i++){
            for(int j=1;j<blen+1;j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1] +1;
                }
                cout<<dp[i][j]<<"  ";
                if(dp[i][j]>Max)
                    Max = dp[i][j];     //保存数组里的最大值
            }
            cout<<endl;
        }
        cout<< Max;
    
    }
    
    
    展开全文
  • 最长公共子序列长度题目 题目 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。 输入样例1: ABCBDAB BDCABA 输出样例1: 4 输入样例2: ...

    最长公共子序列长度

    题目

    求两个字符串的最长公共子序列长度。

    输入格式:
    输入长度≤100的两个字符串。

    输出格式:
    输出两个字符串的最长公共子序列长度。

    输入样例1:

    ABCBDAB
    BDCABA
    

    输出样例1:

    4
    

    输入样例2:

    ABACDEF
    PGHIK
    

    输出样例2:

    0
    

    答案

    using namespace std;
    int main()
    {
    	int dp[105][105];
    	string s1,s2;
    	cin>>s1>>s2;
    	int len1=s1.length(),len2=s2.length();
    	fill(dp[0],dp[0]+105*105,0);
    	for(int i=1;i<=len1;i++)
    	{
    		for(int j=1;j<=len2;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]);
    		}
    	}
    	cout<<dp[len1][len2];
    }
    

    参考

    求最长公共子序列长度

    展开全文
  • 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。 输入样例1: ABCBDAB BDCABA 输出样例1: 4 输入样例2: ABACDEF PGHIK 输出样例2: 0 ...

    题目描述
    求两个字符串的最长公共子序列长度。

    输入格式:
    输入长度≤100的两个字符串。

    输出格式:
    输出两个字符串的最长公共子序列长度。

    输入样例1:

    ABCBDAB
    BDCABA
    

    输出样例1:

    4
    

    输入样例2:

    ABACDEF
    PGHIK
    

    输出样例2:

    0
    

    代码

    在这里学了一个超级好用的初始化二维数组的方法,,**memset()**函数

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	string a,b;
    	cin>>a>>b;
    	int len1=a.size();
    	int len2=b.size();
    	int dp[len1+1][len2+1];
    	memset(dp,0,sizeof(dp));
    	for(int i=0;i<len1;i++){
    		for(int j=0;j<len2;j++){
    			if(a[i]==b[j])
    				dp[i+1][j+1]=dp[i][j]+1;
    			else
    				dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); 
    		}
    	}
    	cout<<dp[len1][len2];
    } 
    
    展开全文
  • 如果两个串的最后结尾的字符相同,其最长公共子序列长度=分别去掉结尾字符剩下的部分的最长公共子序列长度+1; 不相同,则转化为相同:在其中任意一个串上补与另一个串结尾字符相等的字符,然后转化成...
  • 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。 输入样例1: ABCBDAB BDCABA 输出样例1: 4 输入样例2: ABACDEF PGHIK 输出样例2:...
  • 动态规划–求两个字符串的最长公共子序列长度 代码: #include <iostream> #include<string.h> #include<string> using namespace std; const int MAXN=100; const int INF=INT_MAX; int memo...
  • 最长公共子序列 子序列概念: 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如X=(A,B,C,B,D,A,B),X的子序列有(A,B,C,B,A),(A,B,D),(B,C,D,B)。子序列与子串的不同在于子串的元素在原序列中...
  • 假设两个序列 A,B,找两者的最长公共子序列; 第一步: 我们要去找出 A中所有与 B 相同的元素,这些元素在 B中的位置,各自为一个集合;比如 A = { a c f d } ,B = { c f g c a } , 则有 (从 i = 1 ...
  • 最长公共子序列问题Time Limit: 1000 ms Memory Limit: 65536 KiBSubmit StatisticProblem Description 给定两个序列X=Input输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文...
  • 所谓子序列,是指从序列中任意取出...设a的长度为n,b的长度为m,求解a[0,n-1]和b[0,m-1])的最长公共子序列LCS(a[0,n-1], b[0,m-1])无非三种情况 1) a或b为空序列,即m=0或n=0,a[0,n-1]和b[0,m-1])最长公共子序列即...
  • 题目:求两字符串的最长公共子序列长度。 题外话:最长公共子串,子序列问题是被充分讨论的问题,网上一搜一大把,请bing之。 本题只要求求最长公共子序列长度,而不需要记录最长的公共子序列,给予了我们...
  • 动态规划法 经常会遇到复杂问题不能简单地分解成几个问题,而会分解出一系列的问题。简单地采用把大问题分解成子问题,并综合问题的解导出大问题的解的方法,问题求解...【问题】 求两字符序列最长公共
  • 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。 输入样例1: ABCBDAB BDCABA 输出样例1: 4 输入样例2: ABACDEF PGHIK 输出样例2: 0 ...
  • #include<iostream> #include<algorithm> using namespace std; char v1[100100], v2[100100]; //v1:abcd v2:becd 3(bcd) int dp[10010][10010];... //两个字符串的长度 int main() { for (int...
  • 题目Link: ... 递推公式: #include ...//得出两个字符串的长度,如果长度为0直接返回0 ...以上是AC代码,至于怎么得到最长公共子序列,可以从chess[lenA][lenB]开始回溯(Traceback),得到LCS。
  • 最长公共子序列 对一个序列X=(x_0,x_1,…,x_(m-1) ),若序列Y=(y_0,y_1,…,y_(k-1) ),当存在一个严格递增的下标序列(i_0,i_1,…,i_(k-1) ),使得∀j∈[0,k-1], j∈Z,都有x_(i_j )=y_j,则序列Y是序列X的子序列。 ...
  • 该问题是典型的动态规划问题,我们设maxlen(i,j)表示s1左边i个字符与s2左边j个字符的最长公共子序列长度,(i,j)从0开始,那么递推关系很容易找到,就是: if(s1[i-1]==s2[j-1]) { maxlen(i,j)=maxlen(i-1,j-1)+1;...
  • =b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是MAX(a[:m-1]和b[:n]的最长公共子序列长度,a[:m]和b[:n-1]的最长公共子序列长度)。 2.递归定义最优值 3.以自底向上大方式计算出最优值 python代码如下: d
  • 题目:给定两个序列X={x1,x2,…xm},Y={y1,y2,…yn},找出X和Y的最长公共子序列。 分析: 1 最长公共子序列概念 实现明确一个点就是,子序列是一个序列中去掉若干元素后得到的序列,也就是说子序列的元素下标是递增...
  • 问题描述:给定两个序列,例如 X = “ABCBDAB”、Y = “BDCABA”,求它们的最长公共子序列长度。 下面是求解时的动态规划表,可以看出 X 和 Y 的最长公共子序列长度为4: 输出一个最长公共子序列并不难(网上很...
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
     首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后...
  • 动态规划解最长公共子序列(LCS)(附详细填表过程)

    万次阅读 多人点赞 2018-11-20 12:51:34
    最长公共子序列(以下简称LCS): 方法 蛮力法求解最长公共子序列: 动态规划求解最长公共子序列: 分析规律: 做法: 伪代码: 下面演示下c数组的填表过程:(以求ABCB和BDCA的LCS长度为例): 时间复杂度...
  • 最长公共子序列

    2016-04-22 21:22:53
    动态规划问题,求X和Y的最长公共子序列长度以及最长公共子序列。
  • 20170909_最长公共子序列长度LCS
  • 对于两个字符串,请设计一个高效算法,求他们的最长公共子序列长度,这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1,Vi<Vi+1。且A[Ui] == B[Vi]。 给定两个字符串A和B,...
  • 问题描述; 给定两个字符串,求解这两...则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 源代码: public class 最长公共子序列 { private static void LCSLength (int m,int n,char X[],cha...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,181
精华内容 9,672
关键字:

最长公共子序列长度