UVa OJ Longest Common Subsequence

This is the classic LCS problem. Since it only requires you to print the maximum length, the code can be optimized to use only O(m) space (see here).

My accepted code is as follows.

 

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 int lcs(string s, string t) {
 8     int m = s.length(), n = t.length();
 9     vector<int> cur(m + 1, 0);
10     for (int j = 1; j <= n; j++) {
11         int pre = 0;
12         for (int i = 1; i <= m; i++) {
13             int temp = cur[i];
14             cur[i] = (s[i - 1] == t[j - 1] ? pre + 1 : max(cur[i], cur[i - 1]));
15             pre = temp;
16         }
17     }
18     return cur[m];
19 }
20 
21 int main(void) {
22     string s, t;
23     while (getline(cin, s)) {
24         getline(cin, t);
25         printf("%d\n", lcs(s, t));
26     }
27     return 0;
28 }

 

Well, try this problem here and get Accepted :)

更多相关文章
  • 需求:在黑马做安全卫士的时候,功能9设置中心界面如下: 在点击item的时候,复选框会反转状态,同时"自动更新已经关闭"会变换内容和颜色. 可以发现这个界面类似ListView,但又不是ListView,因为它的item数量是固定的,且最后一 item和之前的都不一样.虽然这个看 ...
  • SQLSERVER注入必殺技 必殺技成功條件:1.找到注入點2.數據庫為SQLSERVER3.IIS沒屏蔽錯誤提示 注:因必殺技是我研究N久的心得,經多次改良,成功率極高.請不要用於不合法用途上,否則後果自負. [N] = 第N個表ID=1 and (Select top 1 name from(S ...
  • 作者:张华  发表于:2015-05-07版权声明:可以任意转载,转载时请务必以超链接形式标明文章原始出处和作者信息及本版权声明( http://blog.csdn.net/quqi99 )一,为什么虚机ping不通虚拟所在的tap设一种可能是虚机的MAC地址和其他的重复了,可使用arp命令查看.第 ...
  • 时下,打车软件因其快捷.便利而大受欢迎,但“火爆”背后存在的安全问题也逐渐暴露出来,用户的信息安全更是备受关注.   互联网漏洞曝光平台——乌云网2015年5月向<消费者报道>提供的数据显示,自2014年1月份到2015年5月上旬,共发布59个关于打车软件的安全漏洞,涉及厂商多达9家,其 ...
  • 说明:经常玩Linux系统的朋友多多少少也知道些系统参数优化和怎样增强系统安全性,系统默认的一些参数都是比较保守的,所以我们可以通过调整系统参数来提高系统内存.CPU.内核资源的占用,通过禁用不必要的服务.端口,来提高系统的安全性,更好的发挥系统的可用性.通过自己对Linux了解,对系统调优做了如下 ...
  • 文/未来已来在线旅游岁末盘点是从钱开始的.砸钱"有钱就是任性"是2014年的网络流行语,用在在线旅行行业也恰当.2014年的在线旅游得从年初的砸钱开始说起.2014年年初,同程与携程掀起在线旅游门票价格战,引发围绕着"1元"的促销成为各家在线旅游企业的必杀技. ...
一周排行
  • 如果要设置模糊查询, 一般要在QueryCommand中这样写:  var name = dsQuery.getValue("NAME"); var parameters = command.pa ...
  • 感谢teisan撰写:这几天关于迅雷的负面文章不少,先是版权问题被起诉,后是<南方都市报>报道迅雷扫描用户电脑,而后者的报道内容,其实前段时间已经在网络上炒的沸沸扬扬.版权问题就不说了,目前国内有相当数量 ...
  • 序号 文章标题 链接地址 备注 1 Xen400培训-XenServer最佳实践 http://tasnrh.blog.51cto.com/4141731/1642456 2 Xen与XenServer的区别 htt ...
  • 有个需求测试,需要用webdriver 登录到浪新微博,由于个人比较善长 Webdriver,于是采取了Webdriver+FireFox来实现. 配置环境 a. 必须首先在Eclipse里加载 selenium w ...
  • 本书是个小故事--讲瑞恩如何从一个对送报有兴趣的孩子(开始是因为想得到钱),在家人和朋友的帮助下就成负责的报童的成长与完善,在其中小主人公学到很多商业知识.从书中,每个人都能隐约找到自己,看到少年时自己成长的步伐,非 ...
  • 上一章中使用了一个很重要的概念 — 比例尺( scale ),本节将解说其使用方法. 1. 最大值和最小值 在介绍比例尺( scale )之前,先介绍两个经常和比例尺一起出现的函数,在[第3章]中也出现了. d3.m ...
  • package com.qiyadeng.core;   import java.util.ArrayList; import java.util.Collections; import java.util.Hash ...
  •   a a.m a.m abandon abandon abattoir ability ability able able abnormal abnormal aboard aboard about about a ...
  • http://ued.taobao.org/blog/2012/04/juicer-%E4%B8%80%E4%B8%AAjavascript%E6%A8%A1%E6%9D%BF%E5%BC%95%E6%93%8E%E ...
  • 参照着网上的教程,自己做了一遍,发现教程是错误百出啊,搞得我弄了一个下午才搞好,废话少说,看招! 一.Axis2的下载和安装     读者可以从如下的网址下载Axis2的最新版本:     http://ws.apa ...