首页 > 代码库 > UVA 10405 Longest Common Subsequence
UVA 10405 Longest Common Subsequence
题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1346
Dynamic programming
需要注意的是input里可能含有空行,一行空行也是一个string,所以如果用scanf("%s", string)是不能把空行存进string变量里的。需要用gets或者getline来处理input。
可惜的是我目前对于gets,getline的用法还没有很熟悉,之后会关于这方面的区别做解释。又或者有大神可以帮忙讲解一下,感恩
代码如下:
1 //============================================================================ 2 // Name : test.cpp 3 // Author : 4 // Version : 5 // Copyright : Your copyright notice 6 // Description : Hello World in C++, Ansi-style 7 //============================================================================ 8 9 #include <iostream> 10 #include <math.h> 11 #include <stdio.h> 12 #include <cstdio> 13 #include <algorithm> 14 #include <string.h> 15 #include <cstring> 16 #include <queue> 17 #include <vector> 18 #include <functional> 19 #include <cmath> 20 #define SCF(a) scanf("%d", &a) 21 #define IN(a) cin>>a 22 #define FOR(i, a, b) for(int i=a;i<b;i++) 23 typedef long long Int; 24 using namespace std; 25 26 int main() 27 { 28 char str1[1005]; 29 char str2[1005]; 30 int len1, len2; 31 while (cin.getline(str1, 1005)) 32 { 33 cin.getline(str2, 1005); 34 for (len1 = 0; str1[len1] != ‘\0‘; len1++); 35 for (len2 = 0; str2[len2] != ‘\0‘; len2++); 36 int** match; 37 match = new int*[len1+1]; 38 FOR(i, 0, len1 + 1) 39 match[i] = new int[len2 + 1]; 40 FOR(i, 0, len1 + 1) 41 match[i][0] = 0; 42 FOR(i, 0, len2 + 1) 43 match[0][i] = 0; 44 45 FOR(i, 1, len1 + 1) 46 { 47 FOR(j, 1, len2 + 1) 48 { 49 if (str1[i - 1] == str2[j - 1]) 50 match[i][j] = match[i - 1][j - 1] + 1; 51 else 52 { 53 match[i][j] = max(match[i - 1][j], match[i][j - 1]); 54 } 55 } 56 } 57 58 printf("%d\n", match[len1][len2]); 59 FOR(i, 0, len1 + 1) 60 delete[] match[i]; 61 delete[] match; 62 } 63 return 0; 64 }
UVA 10405 Longest Common Subsequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。