1672 - ACM俱乐部密码
时间限制 : 1 秒
内存限制 : 32 MB
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; }
Java解答
import java.util.*; import java.io.*; import java.math.*; public class Main{ public static Scanner cin=new Scanner(System.in); public static String a,b; public static int[][] dp; public static int lena,lenb; public static void main(String []args){ while(cin.hasNext()){ a=cin.next(); b=cin.next(); lena=a.length(); lenb=b.length(); dp=new int[lena][lenb]; for(int i=0;i<lena;i++){ for(int j=0;j<lenb;j++){ if(i==0&&j==0){ if(a.charAt(i)==b.charAt(j)){ dp[i][j]=1; }else{ dp[i][j]=0; } }else if(i==0){ if(a.charAt(i)==b.charAt(j)){ dp[i][j]=1; }else{ dp[i][j]=dp[i][j-1]; } }else if(j==0){ if(a.charAt(i)==b.charAt(j)){ dp[i][j]=1; }else{ dp[i][j]=dp[i-1][j]; } }else{ if(a.charAt(i)==b.charAt(j)){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]); } } } } System.out.println(dp[lena-1][lenb-1]); } } }
Python解答
#coding=utf-8 def Matrix(rows,cols): matrix = [[[0,'#'] for col in range(cols+1)] for row in range(rows+1)] return matrix def printf(lst,str1,str2): (rows,cols)=(len(str1),len(str2)) print ' '*6, for tmp in str2: print '%s ' % tmp, print print ' '*2, for j in range(cols+1): print '%d:%s' % (lst[0][j][0],lst[0][j][1]), print for i in range(1,rows+1): print '%s ' % str1[i-1], for j in range(cols+1): print '%d:%s' % (lst[i][j][0],lst[i][j][1]), print while True: x=raw_input() y=raw_input() (m,n)=(len(x),len(y)) mat = Matrix(m,n)#已经经过初始化 for i in range(1,m+1): for j in range(1,n+1): #print "i=%d,j=%d" %(i,j) if x[i-1]==y[j-1]: mat[i][j][0]=mat[i-1][j-1][0]+1 mat[i][j][1]='↖' elif mat[i-1][j][0]>=mat[i][j-1][0]: mat[i][j][0]=mat[i-1][j][0] mat[i][j][1]='↑' else: mat[i][j][0]=mat[i][j-1][0] mat[i][j][1]='←' #printf(mat,x,y) print mat[m][n][0]