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元"的促销成为各家在线旅游企业的必杀技. ...
一周排行
  • 1.打开文件:open函数,它接受一个文件名作为唯一的强制参数.如果只提供一个参数的话,那么我们可以获得能获取文件内容的文件对象.如果要向文件内写入内容,则必须提供一个模式参数,open函数中的模式参数只有几个值,如 ...
  • 1.属性 //属性的2种写法 public class person { private string _name; public string Name { get { return _name; } set { ...
  • 栈 栈(stack)是限定尽在表尾进行插入或删除操作的线性表.与线性表类似,栈也有两种存储表示方式. 下面是顺序栈的实现. 1 #include <stdio.h> 2 #include <mall ...
  • 在系统中经常会遇到向数据库中批量插入数据情况,存储过程中没有数组,只有通过字符串分割循环插入,下面是一个本人研究的一个例子: create proc [dbo].[Proc_TestBatchMainDetailIn ...
  • 一.前言 1.由于上一篇文章的标题命名失误,此篇标题写给百度搜索”什么是SharePoint”. 2.关于什么是SharePoint,请参见本人的第一篇文章:http://www.cnblogs.com/iamlil ...
  • 国外媒体报道,维亚康母旗下子公司MTV网络成为了数据窃取的最新受害者,黑客入侵了其计算机系统,并窃取了有关员工的秘密信息. MTV网络周五表示,该公司5000名员工的相关数据遭到非法访问,其中包括姓名.出生日期.社会 ...
  • http://a15030389585.blog.163.com/blog/static/170479963201683912940/ 现在我就自己查到的快捷键总结如下:  制图 Insert or CTRL + E ...
  • <% String path1 = application.getRealPath(request.getRequestURI()); //当前请求的JSP文件的物理路径 String path2 = appl ...
  • 易网科技讯 9月13日消息,微软正式发布了新一代应用软件开发和研发团队管理解决方案Visual Studio 2012和.NET Framework 4.5.Visual Studio 2012提供了更丰富的开发环境 ...
  • 面向服务的架构(SOA)是现在企业部署应用系统主流的做法,但是,著名市场分析机构Gartner公司的一位分析师指出,SOA部署可能会因为七个常见的错误而突然中断. "如果你有没有听说过SOA,那么你肯定生活 ...