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元"的促销成为各家在线旅游企业的必杀技. ...
一周排行
  • CISCO路由器端口状态CSU──channel server unit,DSU──data server unit,DTE──DataTerminalEquipment 1.Serial * is down,lin ...
  • 近期股票市场一路飘红,大"牛市"刺激着人们纷纷投身其中,一股新的投资热潮由此形成,每天到证券交易所要求开户的股民可谓络绎不绝,其中绝大部分选择采取网上交易. "但现在互联网不安全,既想交 ...
  •  Author:Anders小明 目前采用是面向对象设计方法,设计的粒度分为两级:类和方法(属性),类似于数据库设计的表和字段: 在现有实现体系下,一个方法内部将包容多个Use Case:同时因为Use Case本身 ...
  • 先占个位置,下次翻译~ :p There are a few scenarios in which your activity is destroyed due to normal app behavior, suc ...
  • 谨以此文献给在中小规模的软件公司中,希望向配置管理方向发展的朋友. 用几个小故事,展现配置管理在软件公司中的发展过程,同时,也是配置管理员在公司中的发展之路.为了展现主线,故事都比较概括,且本文侧重于配置管理的发展, ...
  • Nginx 重启的另外一种方式,相当于 kill -HUP `cat /usr/local/nginx/logs/nginx.pid`: /usr/local/nginx/sbin/nginx -s reload   ...
  • 泛东协同,赢在执行! 笔者曾在网上看到了一篇小短文<从数据表中取出第n条到第m条的记录的方法>,全文如下: 从publish 表中取出第 n 条到第 m 条的记录:      SELECT TOP m-n ...
  • 本文标签:碎碎念 怎样知道自己爱上了一个人?是不是如果你渴望他爱你,就可以说明你爱上了他?问题是,我最近在看一本书,书里教导我不要期望别人爱自己,而始终要从内心寻找爱,自己爱自己. 那这样的话,是不是我永远也没办法知 ...
  • 在学习UML类图的过程中,UML类图关系是必须要掌握的问题,UML定义的关系主要有六种:依赖.类属.关联.实现.聚合和组合.下面对其定义和表示方法逐一说明. UML类图关系简介 依赖(Dependency):元素A的 ...
  • //赫夫曼树和赫夫曼编码.可运行代码 #include<iostream> using namespace std; typedef struct{ unsigned int weight; unsign ...