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元"的促销成为各家在线旅游企业的必杀技. ...
一周排行
  • 引入: 上文中我们的例子是研究了来自内部的XSS攻击,通过输送一段有害js代码到受害者的机器,让其在受害者的域上运行这段有害JS代码来得到入侵目的.现在我们来看下来自外部的XSS攻击.   实践: 下面还是按照惯例, ...
  • 使用中的问题:  一个Asp.net的CRM项目在Session中存储自定义类型(可序列化的),开始使用的是InProc方式,几个月过去了一切都很和谐,但是最近随着使用人数的增加进程内Session经常丢失,于是业务 ...
  •     题目URL:http://acm.hdu.edu.cn/showproblem.php?pid=1840     判断一个给定的一元二次方程的解的个数.但是这个题目的的一个隐含条件是,a不一定不为0.如果a为 ...
  • groups.vbs时间:2001.2.5版本:1.0作者:沧海笑一声其它:此脚本原作者写于2000年初,沧海用过后觉得不是很好用.它原来的显示方式是wsh的方法,往往要多屏显示,而且不能保存结果我将之改成IE显示的 ...
  • 5月1日凌晨3时30分左右,吉林省通化市胜利路如家酒店发生火灾,最终造成10人死亡.35人受伤.经过公安机关的缜密侦查,7名犯罪嫌疑人已经全部被抓获,目前案件还在审理当中.尽管此次事故涉嫌人为放火,但通化如家酒店的火 ...
  • 大家对深山红叶,矮人DOS工具箱之类的维护光盘应该不陌生了,作为企业,网吧网管,随手准备这样的光盘真的是能解决很多问题.对于网刻,相信很多人也有所了解.但是,在网吧/公司维护机器时.基本上面对的都是无光驱的机器,如果 ...
  • 通过前面的操作,我们已经可以创建一个带有我们自己的PCI的watchdog外设qemu 虚拟机了. 目的: 1. 了解我们的外设情况. 2. 为在guest中开发我们自己的linux PCI驱动程序做准备.   查看 ...
  • 这题的做法非常直观,却又非常不直观 先容许我吐一下槽吧~作者你的英语是读到火星上去了喵?   题目大体是说人类要移民,然后有 n 个人, m 个星球 每个人都有 m 个 0 . 1 数码表示他能否移民到该星球,每个星 ...
  • 巨大的网购市场成了不法分子觊觎的目标.中国反钓鱼网站联盟APAC秘书长齐麟日前表示,2010年新增钓鱼网站175万个,受害网民高达4411万人次,损失超过200亿元.金山网络最新发布的<2010年中国网络购 ...
  • 英文原文:http://www.wpftutorial.net/PasswordBox.html 中文原文:http://blog.csdn.net/oyi319/article/details/6551532 WP ...