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元"的促销成为各家在线旅游企业的必杀技. ...
一周排行
  • 专业的点评还是靠得住的 日,赛门铁克对本年度重大网络威胁做了回顾,内容涉及到目前为止,赛门铁克认为2007年的网络安全大事记,以及对2008年度网络安全的展望. 在赛门铁克发布的2007报告上榜上有名的包括为数众多的 ...
  • 本文主要给大家详细的介绍了对于合法用户被防火墙拒之门外,如何进行操作,并且介绍了故障现象和网络结构,相信看过此文会对你有所帮助. 网络故障现象 这次的客户是本市社会保险局.正月初八全局工作人员上班第一天,许多Intr ...
  •   Flex软件中经常需要使用一些外部的资源,如图片.声音.SWF或字体,第一种你也可以在软件运行的时候引入和载入,第二种可能经常需要直接将这些资源编译(Compile)到软件中,也就是直接嵌入资源(Embeddin ...
  • Linux/Unix 平台下共享库(Shared Library)文件后缀 .so:在 Windows 平台称为动态链接库(Dynamic Link Library),文件名后缀为 .dll.     利用 ctyp ...
  • 无验证码,随意爆破.   POST /seeyon/getAjaxDataServlet?S=ajaxOrgManager&M=isOldPasswordCorrect&CL=true&RVT ...
  • 1.所谓虚拟主机的配置,即url与磁盘目录的绑定 2.在httpd.conf中查询Virtual host,发现有注释说明需要在conf/extra/httpd-vhosts.conf中进行配置. 3.模板: 1 & ...
  • 中文的 http://wenku.baidu.com/view/819b90d676eeaeaad1f3306e.html 情感词典1.知网的情感词典- http://www.keenage.com/html/c_b ...
  •  这题题意不难,就是有n个半径一样的圆,,,,一根绳子把它们围起来问最短的绳长,,,,,,,,,,多画画图就能发现的所有外围的圆圈的圆心距离加上2πR,,, 这题数据给的!!!!!必然是凸多边形而且还是按顺序给! ...
  • 先介绍几个基本概念: lot:工艺制造中按某种方式制成的硅柱 wafer:中文名晶圆,lot切成的薄片,是集成电路的载体,晶圆越大,在同一圆片上生产的IC越多 die:wafer根据需要划分不同的区域,每个区域用于生 ...
  • Unity内容在浏览器通过Unity网络播放器插件加载.HTML代码与这个插件通常不直接通信,而是通过UnityObject的脚本帮助.其主要任务是Unity的内容嵌入一个非常简单的任务,通过从各种浏览器和平台指定发 ...