杭電 HDU ACM 1159 Common Subsequence
來源：程序員人生 發布時間：2015-06-15 08:38:14 閱讀次數：2883次
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26493 Accepted Submission(s): 11771
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing
sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of
the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard
output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
表示好幾天 沒有a過題目了 ，緣由好多，平時課程多死，省賽訓練也常常跑西區，做的題目也不再是水題了，主要學習進程挺費時間 ，我相信只要把某個算法學會了，然后
做的類似的題目就不會浪費時間了。 今天51 也算有了1點點 屬于自己的時間，（其實51還是有好多事情要干）。
參考學習了網上這篇博文，和《算法導論》敘述得差不多，
http://blog.csdn.net/yysdsyl/article/details/4226630
代碼敲的少啊 ，連scanf（）語法也卡了好大會兒。不過 以后知道了……
其實我感覺 ｓｔｒｉｎｇ處理字符串 也挺方便。
#include<iostream >
#include<stdio.h>
#include<cstring>
const int M=500;
using namespace std;
int main()
{
char cnt[M],dic[M];
int c[M][M],k,m;
while(scanf("%s%s",cnt+1,dic+1)!=EOF)
{
int lencnt=strlen(cnt+1);
int lendic=strlen(dic+1);
for(int i=1; i<=lencnt; i++)
c[i][0]=0;
for(int j=0; j<=lendic; j++)
c[0][j]=0;
for( k=1; k<=lencnt; k++)
for( m=1; m<=lendic; m++)
{
if(cnt[k]==dic[m])
{
c[k][m]=c[k⑴][m⑴]+1;
}
else
{
c[k][m]=max(c[k⑴][m],c[k][m⑴]);
}
}
cout<<c[lencnt][lendic]<<endl;
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
