首页 > ACM题库 > 九度OJ > 九度-1042-Coincidence[解题代码]
2013
12-12

九度-1042-Coincidence[解题代码]

题目来源:2008年上海交通大学计算机研究生机试真题

题目描述:

Find a longest common subsequence of two strings.

输入:

First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.

输出:

For each case, output k – the length of a longest common subsequence in one line.

样例输入:
abcd
cxbydz
样例输出:
2

cpp 代码如下:
#include <stdio.h>
#include <string.h>

char str1[102];
char str2[102];
int opt[101][101], len1 ,len2;

int main() {
	//freopen("input.txt", "r", stdin);
	while(gets(str1+1)){
		gets(str2+1);
		 len1 = strlen(str1+1);
		 len2 = strlen(str2+1);
		// printf("%d %d\n", len1, len2);
		 for(int i=0; i<= len1; i++)
			 for(int j=0; j<=len2; j++)
				 opt[i][j] = 0;

		 for(int i=1; i<=len1; i++){
			 for(int j=1; j<=len2; j++){
				 if(str1[i] == str2[j]){
					 opt[i][j] = opt[i-1][j-1]+1;
				 }else{
					 opt[i][j] = opt[i-1][j] > opt[i][j-1] ? opt[i-1][j]:opt[i][j-1];
				 }
			 }
		 }
		 printf("%d\n",opt[len1][len2]);
	}
	return 0;
}
/**************************************************************
	Problem: 1042
	User: coder
	Language: C++
	Result: Accepted
	Time:0 ms
	Memory:1060 kb
****************************************************************/


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。