POJ 2250 （最长公共子序列LCS）

灰太狼 2024-02-17 19:26 39阅读 0赞

题意：给出两段单词，找出他们的最长公共子序列并打印

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn1=30+2;
    const int maxn2=100+5;
    char s1[maxn2][maxn1];
    char s2[maxn2][maxn1];
    int dp[maxn2][maxn2];
    int pre[maxn2][maxn2];
    
    void print(int len1,int len2){
    	if(len1==0 || len2==0)return ;
    	if(pre[len1][len2]==0){
    		print(len1-1,len2-1);
    		printf("%s ",s1[len1-1]);
    	}
    	else if(pre[len1][len2]==1)
    	    print(len1-1,len2);
    	else print(len1,len2-1);
    }
    int main(){
         while(scanf("%s",s1[0])==1){
         	int len1=1;
         	while(strcmp(s1[len1-1],"#"))
         	      scanf("%s",s1[len1++]);
         	scanf("%s",s2[0]);
         	int len2=1;
            while(strcmp(s2[len2-1],"#"))
                  scanf("%s",s2[len2++]);
            
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=len1;i++)
            	for(int j=1;j<=len2;j++)
            		if(strcmp(s1[i-1],s2[j-1])==0){
            		  dp[i][j]=dp[i-1][j-1]+1;
    				  pre[i][j]=0;		
    				}
            		else if(dp[i-1][j]>dp[i][j-1]){
            			dp[i][j]=dp[i-1][j];
            			pre[i][j]=1;
    				}
    				else {
    					dp[i][j]=dp[i][j-1];
    					pre[i][j]=-1;
    				}
    			print(len1-1,len2-1);
    			printf("\n");
    	 } 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2250 （最长公共子序列LCS）

题意：给出两段单词，找出他们的最长公共子序列并打印 AC代码： include<cstdio> include<cstring> include<a

灰太狼/ 2024年02月17日 19:26/ 0 赞/ 40 阅读

相关最长公共子序列（LCS）

最长公共子序列（LCS） problem [leetcode: 1035. 不相交的线][leetcode_ 1035.] > dp\[i\]\[j\]：nums

朴灿烈づ我的快乐病毒、/ 2022年10月14日 13:54/ 0 赞/ 156 阅读

相关最长公共子序列（LCS）

这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。算法分析：采用动态规划方法来解决问题，将最长公共子

分手后的思念是犯贱/ 2022年09月29日 15:52/ 0 赞/ 155 阅读

相关最长公共子序列LCS问题

好久没有写博客了，刚才在网上看了清华大学的数据结构公开课，链接：https://www.xuetangx.com 可以注册个账号去听数据结构课程，老师讲的特好。我的代码是按

冷不防/ 2022年09月17日 15:21/ 0 赞/ 192 阅读

相关 poj1458-Common Subsequence（最长公共子序列，LCS）

Common Subsequence <table style="text-align:center"> <tbody> <tr> <td><strong>

墨蓝/ 2022年08月04日 12:36/ 0 赞/ 59 阅读

相关 LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；设：主串长度为n；子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

绝地灬酷狼/ 2022年08月03日 14:57/ 0 赞/ 158 阅读

相关最长公共子序列(LCS)问题

> > 程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言程序员编程艺术系列重新开始创作了（前十章，请参考[程序员编程艺术第一~十章集锦与总结][Li

你的名字/ 2022年07月12日 03:15/ 0 赞/ 165 阅读

相关最长公共子序列Lcs

1.给出两个字符串A B，求A与B的最长公共子序列的长度（子序列不要求是连续的）。 2.给出两个字符串A B，求A与B的最长公共子序列子串（子序列不要求是连续的）。

浅浅的花香味﹌/ 2022年06月12日 10:55/ 0 赞/ 169 阅读

相关最长公共子序列（LCS）算法

一、最长公共字串与最长公共子序列最长公共子串（Longest Common Substirng）子串是串的一个连续的部分，子串中字符的位置必须连续。例如：有

Love The Way You Lie/ 2022年06月05日 01:10/ 0 赞/ 238 阅读

相关求最长公共子序列（LCS）

题目：求最长公共子序列（LCS）思路：经典的动态规划法， c\[i,j\]表示Xi与Yj的最长公共子序列，其中 Xi = \{x1，、、、xi\}

傷城~/ 2022年05月30日 02:59/ 0 赞/ 185 阅读