首页 > 代码库 > UVA10100:Longest Match（最长公共子序列）&&HDU1458Common Subsequence ( LCS）
UVA10100:Longest Match（最长公共子序列）&&HDU1458Common Subsequence ( LCS）
题目链接：http://blog.csdn.net/u014361775/article/details/42873875
题目解析：
给定两行字符串序列，输出它们之间最大公共子单词的个数
对于给的两个序列X 和 Y，用i 和 j分别作为它们的前缀指针，f[i][j]表示序列X的前缀Xi 和 序列Y的前缀Yi 的最长公共子序列的长度，在这道题中，可把每一个单词当作一个字符来进行比较。
当 i | j 为0时 ，此 f[i][j] = 0;
当 i!=0 && j!=0 && Xi==Yi 时 f[i][j] = f[i-1][j-1] + 1;
当 i!=0 && j!=0 && Xi!=Yi 时 f[i][j] = max ( f[i-1][j] + f[i][j-1] );
以上是对最长公共子序列的求法。
我这题做了一下午，因为不会使用C++里面的函数，所以我用C语言写的，总是出现错误，之后错误没有了交上去却一直ＷＡ，后来一看题解才知道，字符串里面包括数字，坑啊，
改完后交时，ＵＶＡ却崩了，等了两个多小时才交上，坎坷ＡＣ路。
代码：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <math.h>using namespace std;char str[20100],st2[20100];char a[1002][22],b[1002][22];int f[1002][1002];int main(){ int K=0,tt=0,l,t,t2,l2,ff; while(gets(str)!=NULL) { tt=0; t2=0; t=0; gets(st2); ff=0; l=strlen(str); l2=strlen(st2); for(int i=0; i<l; i++) { if((str[i]>=‘A‘&&str[i]<=‘Z‘)||(str[i]>=‘a‘&&str[i]<=‘z‘)||(str[i]>=‘0‘&&str[i]<=‘9‘)) { a[tt][t++]=str[i]; ff=1; } else { if(t) { a[tt][t]=‘\0‘; t=0; } if((i+1<l)&&((str[i+1]>=‘a‘&&str[i+1]<=‘z‘)||(str[i+1]>=‘A‘&&str[i+1]<=‘Z‘)||(str[i+1]>=‘0‘&&str[i+1]<=‘9‘))) { tt++; } } } if(((str[l-1]>=‘A‘&&str[l-1]<=‘Z‘)||(str[l-1]>=‘a‘&&str[l-1]<=‘z‘)||(str[l-1]>=‘0‘&&str[l-1]<=‘9‘))&&t>0) { a[tt][t]=‘\0‘; } printf("%2d. ",++K); if(l==0||l2==0) { printf("Blank!\n"); continue; } if(ff==0) { printf("Length of longest match: 0\n"); continue; } t=0; for(int i=0; i<l2; i++) { if((st2[i]>=‘A‘&&st2[i]<=‘Z‘)||(st2[i]>=‘a‘&&st2[i]<=‘z‘)||(st2[i]>=‘0‘&&st2[i]<=‘9‘)) { b[t2][t++]=st2[i]; ff=2; } else { if(t) { b[t2][t]=‘\0‘; t=0; } if((i+1<l2)&&((st2[i+1]>=‘0‘&&st2[i+1]<=‘9‘)||(st2[i+1]>=‘a‘&&st2[i+1]<=‘z‘)||(st2[i+1]>=‘A‘&&st2[i+1]<=‘Z‘))) { t2++; } } } if(((st2[l2-1]>=‘A‘&&st2[l2-1]<=‘Z‘)||(st2[l2-1]>=‘a‘&&st2[l2-1]<=‘z‘)||(st2[l2-1]>=‘0‘&&str[l2-1]<=‘9‘))&&t>0) { b[t2][t]=‘\0‘; } if(ff!=2) { printf("Length of longest match: 0\n"); continue; } for(int i=0; i<=tt+1; i++) { f[i][0]=0; } for(int i=0; i<=t2+1; i++) { f[0][i]=0; } for(int i=1; i<=tt+1; i++) { for(int j=1; j<=t2+1; j++) { if(strcmp(a[i-1],b[j-1])==0) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } } printf("Length of longest match: %d\n",f[tt+1][t2+1]); } return 0;}
HDU1458Common Subsequence:模版题
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>#define N 400#define inf 0x3f3f3f3ftypedef int ll;using namespace std;int dp[600][600],l1,l2;int main(){ char a[600],b[600]; while(scanf("%s%s",a,b)!=EOF) { l1=strlen(a); l2=strlen(b); for(int i=0; i<l1; i++) { dp[i][0]=0; } for(int i=0; i<l2; i++) { dp[0][i]=0; } for(int i=1; i<=l1; i++) { for(int j=1; j<=l2; j++) { if(a[i-1]==b[j-1]) { dp[i][j]=1+dp[i-1][j-1]; } else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } printf("%d\n",dp[l1][l2]); } return 0;}
非常棒的博客：地址：http://www.cnblogs.com/wb-DarkHorse/archive/2012/11/15/2772520.html
一：LCS解析
首先看下什么是子序列？定义就不写了，直接举例一目了然。如对于字符串：“student”，那么su，sud，sudt等都是它的子序列。它可以是连续的也可以不连续出现，如果是连续的出现，比如stud，一般称为子序列串，这里我们只讨论子序列。
什么是公共子序列？很简单，有两个字符串，如果包含共同的子序列，那么这个子序列就被称为公共子序列了。如“student”和“shade”的公共子序列就有“s”或者“sd”或者“sde”等。而其中最长的子序列就是所谓的最长公共子序列(LCS)。当然，最长公共子序列也许不止一个，比如：“ABCBDAB”和“BDCABA”，它们的LCS为“BCBA”，“BCAB”，“BDAB”。知道了这些概念以后就是如何求LCS的问题了。
通常的算法就是动态规划(DP)。假设现在有两个字符串序列：X={x1,x2,...xi...xm},Y={y1,y2,...yj...yn}。如果我们知道了X={x1,x2,...xi-1}和Y={y1,y2,...yj-1}的最大公共子序列L，那么接下来我们可以按递推的方法进行求解：
1)如果xi==yj,那么{L,xi(或yj)}就是新的LCS了，其长度也是len(L)+1。这个好理解，即序列{Xi,Yj}的最优解是由{Xi-1,Yj-1}求得的。
2)如果xiyj,那么可以转换为求两种情况下的LCS。
A: X={x1,x2,...xi}与Y={y1,y2,...yj-1}的LCS，假设为L1
B: X={x1,x2,...xi-1}与Y={y1,y2,...yj}的LCS，假设为L2
那么xiyj时的LCS=max{L1,L2},即取最大值。同样，实际上序列{Xi,Yj-1}和{Xi-1,Yj}都可以由{Xi-1,Yj-1}的最优解求得。
怎么样，是不是觉得这种方法很熟悉？当前问题的最优解总是包含了一个同样具有最优解的子问题，这就是典型的DP求解方法。好了，直接给出上面文字描述解法中求LCS长度的公式：
这里用一个二维数组存储LCS的长度信息，i，j分别表示两个字符串序列的下标值。这是求最大公共子序列长度的方法，如果要打印出最大公共子序列怎么办？我们还需要另外一个二维数组来保存求解过程中的路径信息，方便最后进行路径回溯，找到LCS。如果看着很含糊，我下面给出其实现过程。
UVA10100:Longest Match（最长公共子序列）&&HDU1458Common Subsequence ( LCS）