博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVa 10100 - Longest Match
阅读量:5754 次
发布时间:2019-06-18

本文共 1490 字,大约阅读时间需要 4 分钟。

题目:求两组字符串中最大的按顺序出现的同样单词数目。

分析: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 
#include
#include
#include
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;}

转载地址:http://wdckx.baihongyu.com/

你可能感兴趣的文章
springcloud 学习-eureka搭建-为eureka添加认证
查看>>
jQuery插件的开发
查看>>
基础,基础,还是基础之JAVA基础
查看>>
如何成为一个C++高级程序员
查看>>
ant android 打包签名和渠道
查看>>
一个简单的接口,被调用并同步给出响应的方法
查看>>
Hadoop序列化与压缩
查看>>
由“男怕入错行”说开去
查看>>
CGImageSource对图像数据读取任务的抽象
查看>>
我的友情链接
查看>>
xss test
查看>>
也谈svn分支与合并
查看>>
显式锁(第十三章)
查看>>
LBS“他爹”GIS
查看>>
SCCM的证书配置PKI
查看>>
看linux书籍做的一些重要笔记(2011.07.03更新)
查看>>
CString、Char* ,char [20]、wchar_t、unsigned short转化
查看>>
从案例学RxAndroid开发(上)
查看>>
Redis学习手册(内存优化)
查看>>
浅尝TensorFlow on Kubernetes
查看>>