1672 - ACM俱乐部密码
ACM俱乐部的墙上写着两行密码字符串，据说能破解其中奥秘的人计算机考研一定过。
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
现在求ACM俱乐部两行密码字符串的最长公共子串的长度。
题目输入
每组测试数据输入两行，每行输入一个字符串（长度<=100）。
题目输出
每组测试数据输出一行，输出ACM俱乐部两行密码字符串的最长公共子串的长度。
输入/输出样例
题目输入
BDCABA ABCBDAB JXVTEWSNHACJDE LDAAJNOPPERLJBPUUNHWSYYODMGW
题目输出
4 5
C语言解答
/* * ===================================================================================== * * Filename: 908.c * * Description: hahah LCS * * Version: 1.0 * Created: 2013/9/8 22:08:10 * Revision: none * Compiler: gcc * * Author: mdk-vim.cpp-c (mdk), mengdaikun@gmail.com * Company: cjluacm-vim-mdk * * ===================================================================================== */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define MAX 100 int dp[MAX][MAX]; int max(int a, int b) { return a > b ? a : b ; } int main() { //freopen("a.in","r",stdin); char str1[MAX],str2[MAX]; int i,j; int len1,len2; while(~scanf("%s %s",str1,str2)) { len1 = strlen(str1); len2 = strlen(str2); for(i = 0 ; i <= len1 ; i++) dp[0][i] = 0; for(j = 0 ; j <= len2 ; j++) dp[j][0] = 0; for(j = 0 ; j < len1 ; j++) { for(i = 0 ; i < len2 ; i++) { if(str1[j] == str2[i]) dp[i+1][j+1] = dp[i][j]+1; else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]); } } printf("%d\n",dp[len2][len1]); } return 0; }
C++解答
#include <stdio.h> #include <string.h> // directions of LCS generation enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp}; ///////////////////////////////////////////////////////////////////////////// // Get the length of two strings' LCSs, and print one of the LCSs // Input: pStr1 - the first string // pStr2 - the second string // Output: the length of two strings' LCSs ///////////////////////////////////////////////////////////////////////////// int LCS(char* pStr1, char* pStr2) { if(!pStr1 || !pStr2) return 0; size_t length1 = strlen(pStr1); size_t length2 = strlen(pStr2); if(!length1 || !length2) return 0; size_t i, j; // initiate the length matrix int **LCS_length; LCS_length = (int**)(new int[length1]); for(i = 0; i < length1; ++ i) LCS_length[i] = (int*)new int[length2]; for(i = 0; i < length1; ++ i) for(j = 0; j < length2; ++ j) LCS_length[i][j] = 0; // initiate the direction matrix int **LCS_direction; LCS_direction = (int**)(new int[length1]); for( i = 0; i < length1; ++ i) LCS_direction[i] = (int*)new int[length2]; for(i = 0; i < length1; ++ i) for(j = 0; j < length2; ++ j) LCS_direction[i][j] = kInit; for(i = 0; i < length1; ++ i) { for(j = 0; j < length2; ++ j) { if(i == 0 || j == 0) { if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = 1; LCS_direction[i][j] = kLeftUp; } else LCS_length[i][j] = 0; } // a char of LCS is found, // it comes from the left up entry in the direction matrix else if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1; LCS_direction[i][j] = kLeftUp; } // it comes from the up entry in the direction matrix else if(LCS_length[i - 1][j] > LCS_length[i][j - 1]) { LCS_length[i][j] = LCS_length[i - 1][j]; LCS_direction[i][j] = kUp; } // it comes from the left entry in the direction matrix else { LCS_length[i][j] = LCS_length[i][j - 1]; LCS_direction[i][j] = kLeft; } } } return LCS_length[length1 - 1][length2 - 1]; } ///////////////////////////////////////////////////////////////////////////// // Print a LCS for two strings // Input: LCS_direction - a 2d matrix which records the direction of // LCS generation // pStr1 - the first string // pStr2 - the second string // row - the row index in the matrix LCS_direction // col - the column index in the matrix LCS_direction ///////////////////////////////////////////////////////////////////////////// int main() { char a[100],b[100]; while(scanf("%s%s",a,b)!=EOF) printf("%d\n",LCS(a,b)); return 0; }