3970 - 【二维一边推1.1】最长公共子序列 LCS加强版
给出两个字符串 S1 和 S2 求它们最长公共子序列的长度。
什么是最长公共子序列呢？
比如：
S1:='abbccdss'
S2:='aeebfcaadb'
那么S1和S2的最长公共子序列就是："abcd". 这个说明最长公共子序列强调位置的前后关系不变，但不在乎是否连续。另外 最长公共子序列不唯一。任意输出一个最长的公共子序列即可。
【输入格式】
读入两行，分别是S1和S2（ 长度不大于1000）。
【输出格式】
输出一个整数。即为最长公共子序列的长度。
【输入样例】
abbccdss
aeebfcaadb
【输出样例】
4
abcd
Input
Output
Examples
Input
Output
Solution C++
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; struct node { int x,y; }p[1001][1001]; char s1[1100], s2[1100],s[1100]; int f[1100][1100],len1,len2; int mymax ( int x, int y ){ return x > y ? x : y; } int main () { scanf ( "%s", s1 + 1 ); len1 = strlen ( s1 + 1 ); scanf ( "%s", s2 + 1 ); len2 = strlen ( s2 + 1 ); memset(f,0,sizeof(f)); for (int i = 1; i <= len1; i ++ ) { for (int j = 1; j <= len2; j ++ ) { if ( s1[i] == s2[j] ) { f[i][j] = f[i - 1][j - 1] + 1; p[i][j].x=i; p[i][j].y=j; } else { if( f[i-1][j] > f[i][j-1] ) { f[i][j]=f[i-1][j]; p[i][j]=p[i-1][j]; } else { f[i][j]=f[i][j-1]; p[i][j]=p[i][j-1]; } } } } printf ( "%d\n", f[len1][len2] ); int x=len1,y=len2,len=0; while( f[x][y]>0) { int xx,yy; xx=x;yy=y; s[++len]=s1[ p[xx][yy].x ];// s[++len]=s2[ p[xx][yy].y]; x=p[xx][yy].x-1; y=p[xx][yy].y-1; } for(int i=len;i>=1;i--) printf("%c",s[i]); printf("\n"); return 0; }