本文共 1121 字,大约阅读时间需要 3 分钟。
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
Input
输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。
Output
每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。
Sample Input
ABCBDABBDCABA
Sample Output
4
代码如下:
#include#include #include int main(){ char X[500],Y[510]; int c[510][510]= {0,}; while(scanf("%s%s",X,Y)!=EOF) { int i,j,x,y; x=strlen(X); y=strlen(Y); for(i=0; i<=x; i++) { c[i][0]=0; } for(j=0; j<=y; j++) { c[0][j]=0; } for(i=1; i<=x; i++) { for(j=1; j<=y; j++) { if(X[i-1]==Y[j-1]) { c[i][j]=c[i-1][j-1]+1; } else { if(c[i-1][j]>c[i][j-1]) { c[i][j]=c[i-1][j]; } else c[i][j]=c[i][j-1]; } } } printf("%d\n",c[x][y]); } return 0;}
转载地址:http://dkhwi.baihongyu.com/