题目链接：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[],st2[];
char a[][],b[][];
int f[][]; int main()
{
int K=,tt=,l,t,t2,l2,ff;
while(gets(str)!=NULL)
{
tt=;
t2=;
t=;
gets(st2);
ff=;
l=strlen(str);
l2=strlen(st2);
for(int i=; i<l; i++)
{
if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')||(str[i]>=''&&str[i]<=''))
{
a[tt][t++]=str[i];
ff=;
}
else
{
if(t)
{
a[tt][t]='\0';
t=;
}
if((i+<l)&&((str[i+]>='a'&&str[i+]<='z')||(str[i+]>='A'&&str[i+]<='Z')||(str[i+]>=''&&str[i+]<='')))
{
tt++;
}
}
}
if(((str[l-]>='A'&&str[l-]<='Z')||(str[l-]>='a'&&str[l-]<='z')||(str[l-]>=''&&str[l-]<=''))&&t>)
{
a[tt][t]='\0';
}
printf("%2d. ",++K);
if(l==||l2==)
{
printf("Blank!\n");
continue;
}
if(ff==)
{
printf("Length of longest match: 0\n");
continue;
} t=;
for(int i=; i<l2; i++)
{
if((st2[i]>='A'&&st2[i]<='Z')||(st2[i]>='a'&&st2[i]<='z')||(st2[i]>=''&&st2[i]<=''))
{
b[t2][t++]=st2[i];
ff=;
}
else
{
if(t)
{
b[t2][t]='\0';
t=;
}
if((i+<l2)&&((st2[i+]>=''&&st2[i+]<='')||(st2[i+]>='a'&&st2[i+]<='z')||(st2[i+]>='A'&&st2[i+]<='Z')))
{
t2++;
}
}
}
if(((st2[l2-]>='A'&&st2[l2-]<='Z')||(st2[l2-]>='a'&&st2[l2-]<='z')||(st2[l2-]>=''&&str[l2-]<=''))&&t>)
{
b[t2][t]='\0';
}
if(ff!=)
{
printf("Length of longest match: 0\n");
continue;
}
for(int i=; i<=tt+; i++)
{
f[i][]=;
}
for(int i=; i<=t2+; i++)
{
f[][i]=;
}
for(int i=; i<=tt+; i++)
{
for(int j=; j<=t2+; j++)
{
if(strcmp(a[i-],b[j-])==)
f[i][j]=f[i-][j-]+;
else f[i][j]=max(f[i-][j],f[i][j-]);
}
}
printf("Length of longest match: %d\n",f[tt+][t2+]);
}
return ;
}
HDU1458Common Subsequence:模版题
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define N 400
#define inf 0x3f3f3f3f
typedef int ll;
using namespace std;
int dp[][],l1,l2;
int main()
{
char a[],b[];
while(scanf("%s%s",a,b)!=EOF)
{
l1=strlen(a);
l2=strlen(b);
for(int i=; i<l1; i++)
{
dp[i][]=;
}
for(int i=; i<l2; i++)
{
dp[][i]=;
}
for(int i=; i<=l1; i++)
{
for(int j=; j<=l2; j++)
{
if(a[i-]==b[j-])
{
dp[i][j]=+dp[i-][j-];
}
else dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
printf("%d\n",dp[l1][l2]);
}
return ;
}
非常棒的博客：地址：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。如果看着很含糊，我下面给出其实现过程。