首页 > 代码库 > UVa 10100 - Longest Match
UVa 10100 - Longest Match
题目:求两组字符串中最大的按顺序出现的相同单词数目。
分析:dp,最大公共子序列(LCS)。把单词整个看成一个元素比较即可。
状态:f(i,j)为s1串前i个单词与s2串前j个单词的最大匹配数;
转移:f(i,j)= max(f(i-1,j),f(i,j-1)){ s1[i] ≠ s2[j] };
f(i-1,j-1)+ 1。
这里的字母包括数字
说明:数据输入,需要先分解成单词,然后计算即可。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; char buf[1001]; char s1[1001][22]; char s2[1001][22]; int f[1001][1001]; int letter(char c) { if (c >= 'a' && c <= 'z') return 1; if (c >= 'A' && c <= 'Z') return 1; if (c >= '0' && c <= '9') return 1; return 0; } int getword(char s[][22], char *t) { int move = 0,count = 0; while (t[move]) { while (t[move] && !letter(t[move])) move ++; if (!t[move]) break; int now = move; while (letter(t[move])) move ++; int save = 0; while (now < move) s[count][save ++] = t[now ++]; s[count][save] = 0; count ++; } return count; } int main() { int blank = 0,l1,l2,cases = 1; while (gets(buf)) { if (!strlen(buf)) blank = 1; l1 = getword(s1, buf); gets(buf); if (!strlen(buf)) blank = 1; l2 = getword(s2, buf); printf("%2d. ",cases ++); if (blank) { printf("Blank!\n"); blank = 0; }else { for (int i = 0 ; i <= l1 ; ++ i) for (int j = 0 ; j <= l2 ; ++ j) f[i][j] = 0; for (int i = 1 ; i <= l1 ; ++ i) for (int j = 1 ; j <= l2 ; ++ j) { f[i][j] = f[i-1][j]; if (f[i][j] < f[i][j-1]) f[i][j] = f[i][j-1]; if (!strcmp(s1[i-1], s2[j-1])) f[i][j] = f[i-1][j-1]+1; } printf("Length of longest match: %d\n",f[l1][l2]); } } return 0; }
UVa 10100 - Longest Match
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。