位置:首页 » 技术 » POJ 2774 最长公共子串

POJ 2774 最长公共子串

日期:2014-01-02 阅读:0num
Advertisement

题意:

给定2个字符串,求最长公共子串的长度

思路:

把两个字符串相连得到S,则他们的公共子串就是部分S的后缀子串的前缀。

因为是相同的子串,所以sa必然是相邻的,因此扫一下height,若sa[i] 与 sa[i-1] 的后缀分别在分割符$前后,那就是两个字符串的后缀,求其最长公共前缀(即height[i])就是一个公共子串。

#include
#include
#include
#include
#include
#include
using namespace std;
#define rank Rank
/*
* 后缀数组
* DC3算法,复杂度O(n)
* 所有的相关数组都要开三倍

*待排序数组长度为n,放在0~n-1中,在最后面补一个0
*da(str ,n+1,sa,rank,height, , );//注意是n+1;
*例如:
*n = 8;
*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0,其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值,rank[n]必定为0无效值
*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值,sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*
*/
const int MAXN=301000;
int rank[MAXN],height[MAXN];
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)= 0;i--)
        b[--wss[wv[i]]] = a[i];
}
void dc3(int *r,int *sa,int n,int m)
{
    int i, j, *rn = r + n;
    int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p;
    r[n] = r[n+1] = 0;
    for(i = 0;i  len1) || (sa[i]>len1 && sa[i-1] 
相关文章
  • POJ 2774 最长公共子串

    题意: 给定2个字符串,求最长公共子串的长度 思路: 把两个字符串相连得到S,则他们的公共子串就是部分S的后缀子串的前缀. 因为是相同的子串,所以sa必然是相邻的,因此扫一下height,若sa[i] 与 sa[i-1] 的后缀分别在分割符$前后,那就是两个字符串的后缀,求其最长公共前缀(即height[i])就是一个公共子串. #include #include #include #include #include #include using namespace std; #define r

  • POJ 1226(最长公共子串含逆序)

    Substrings Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 9639 Accepted: 3319 Description 请找出一些串的最长'正/逆'子串,使它为所有的串的子串(即使是逆序也认为包含). Input 第一行为数据数t,(1 <= t <= 10), 对每组数据而言:第一行为字符串个数 n (1 <= n <= 100),接下来n行为字符串(长度不超过100) . Output 每行一个

  • POJ 标题2774 Long Long Message(后缀数组,求最长公共子串长度)

    POJ 题目2774 Long Long Message(后缀数组,求最长公共子串长度) Long Long Message Time Limit: 4000MS Memory Limit: 131072K Total Submissions: 23696 Accepted: 9705 Case Time Limit: 1000MS Description The little cat is majoring in physics in the capital of Byterland. A p

  • 后缀数组之最长公共子串 poj 2774

    用后缀数组求两个串的最长公共子串的长度 详见罗穗骞的论文 [cpp] #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #define MAXN 1000005 using namespace std; int r[MAXN]; int wa[MAXN],

  • POJ 2774 后缀数组:求最长公共子串

    思路:其实很简单,就是两个字符串连接起来,中间用个特殊字符隔开,然后用后缀数组求最长公共前缀,然后不同在两个串中,并且最长的就是最长公共子串了. 注意的是:用第一个字符串来判断是不是在同一个字符中,刚开始用了第二个字符的长度来判断WA了2发才发现. #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #defi

  • LCP poj 2217 寻觅最长公共子串

    LCP poj 2217 寻找最长公共子串 题目:http://poj.org/problem?id=2217 首先解释,DP中的最长公共子序列和此处的最长公共子串区别-------------------序列可以是不连续的,但是子串是连续的 其次,LCP,lcp[i]就是lcp[rank[i]]和lcp[rank[i]+1]的最长公共前缀,那么把两个字符串接起来,然后找最长的lcp,就是答案 思路还是比较清晰的 上代码: /***********************************

  • poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津市预选题

    poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津预选题 题目:http://poj.org/problem?id=1226 http://acm.hdu.edu.cn/showproblem.php?pid=1238 其实用hash+lcp可能也可以,甚至可能写起来更快,不过我没试,我最近在练习后缀数组,所以来练手 后缀数组的典型用法之一----------------后缀数组+lcp+二分 思路:1.首先将所有的字符串每读取一个

  • poj-3450 KMP求多个字符串的最长公共子串

    poj--3450 KMP求多个字符串的最长公共子串 思路与前面的3080一样 代码如下: #include<iostream> #include<cstdio> #include<cstring> using namespace std; char str1[220],str2[220]; int next[220],n; char ch[4400][220]; void GetNext() { int j=0; int len=strlen(str2+1); nex

  • POJ 2127 最长公共回升子序列

    POJ 2127 最长公共上升子序列 动态规划法: #include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include &

  • 求最长公共子串 递归写的

    求助 求最长公共子串 递归写的 程序运行不过 帮我看看哪里错误了 基本思想还是以前的求解方法:对于字符串a,b,尽量用b的最大的子字符串c去匹配另外一个字符串a,如果c不是a的子串,那么用字符串b的长度比b少1的子串去匹配a,直到匹配到了为止或者子串的长度为0. #include<stdio.h> #include<stdlib.h> #include<iostream> #include<string.h> using namespace std; int

  • 求两个字符串的最长公共子串 (字母务须相邻)

    求两个字符串的最长公共子串 (字母必须相邻) 上一篇<求最长公共子串(可以不相邻)>的另一种变换题目,这个相对于上一篇,稍稍简单,不过这个算法的时间复杂度不太好,更简单的算法,有时间我再整理下. 问题:求最长公共子串,字符必须相邻. 代码: public class common { public static void findCommon(String s1, String s2) { int i;//第一个游标从0 ~ length-1游走 int j;//第二个游标从i+1 ~ len

  • 求两个字符串的最长公共子串(字母可以不紧邻,但是顺序不变)

    求两个字符串的最长公共子串(字母可以不相邻,但是顺序不变) 不知道为什么笔试总是遇到这些题目,看来经典算法,大家都喜欢啊,这个是LCS问题,动态规划. 问题:求两个字符串的最长公共子串,字母可以不相邻,但是顺序不变 代码: public class lcs { public static void LCS_Print(String str1, String str2) { int length1 = str1.length(); int length2 = str2.length(); int

  • 应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串有关问题

    应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串问题 /** * @see IOI2009国家集训队论文<后缀数组--处理字符串的有力工具> * @author leon * */ public class SuffixArray { int max_char = '\uffff'; char separator = '$'; char eof = '#'; int[][] rmq; String text = ""; int min_len = Integer.MA

  • 从优化到再优化,最长公共子串

    概览 最长公共子串问题的基本表述为: 给定两个字符串,求出它们之间最长的相同子字符串的长度. 最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同,然后取得相同最长的那个.对于一个长度为n的字符串,它有n(n+1)/2 个非空子串.所以假如两个字符串的长度同为n,通过比较各个子串其算法复杂度大致为O(n4).这还没有考虑字符串比较所需的时间.简单想想其实并不需要取出所有的子串,而只要考虑每个子串的开始位置就可以,这样可以把复杂度减到O(n3). 但这个问题最好的解决办法是动态规划

  • 软件工程师面试题精选100题(20)-最长公共子串

    程序员面试题精选100题(20)-最长公共子串 这个题目待研究... 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串. 分析:求最长公共子串(Longest Co

  • SPOJ1811最长公共子串有关问题(后缀自动机)

    SPOJ1811最长公共子串问题(后缀自动机) 题目:http://www.spoj.com/problems/LCS/ 题意:给两个串A和B,求这两个串的最长公共子串. 分析:其实本题用后缀数组的DC3已经能很好的解决,这里我们来说说利用后缀自动机如何实现. 对于串A和B,我们先构造出串A的后缀自动机,那么然后用B串去匹配,对于B,我们一位一位地扫描,维护一个ans值,表示从 B串的开始到B[i]的这个子串与A的最长公共子串. 假设现在到B[i-1]的最长公共子串长度为ans,然后我们来看B[

  • 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串

    找工作知识储备(2)---数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 作者:寒小阳 时间:2013年9月. 出处:http://blog.csdn.net/han_xiaoyang/article/details/11969497. 声明:版权所有,转载请注明出处,谢谢. 0.前言 这一部分的内容原本是打算在之后的字符串或者数组专题里面写的,但看着目前火热进行的各家互联网公司笔试面试中,出现了其中的一两个内容,

  • 动态规划求解最长公共子串中的有关问题

    动态规划求解最长公共子串中的问题 今天学习了动态规划的相关思想,随后找了一些经典的题目希望能加深一下印象.然而在求解"最长公共子串"的问题时却发现了一些问题. 一般来说,在求解这类问题的时候,大都依据以下原理: 定义lcs[i][j]为序列"a0,a1,-,ai-2"和"b0,b1,-,bj-1"的最长公共子序列的长度,计算lcs[i] [j]可递归地表述如下: (1)lcs[i][j] = 0 如果i=0或j=0: (2)lcs[i][j] =

  • 【CodeCraft赛事】Problem 7——X-man(最长公共子串LCS变种) 【CodeCraft赛事】Problem 7——X-man(最长公共子串LCS变种)

    [CodeCraft比赛]Problem 7--X-man(最长公共子串LCS变种) 题目:点击打开链接 Question 7 Problem Statement Dr. Charles Xavier is trying to check the correlation between the DNA samples of Magneto and Wolverine. Both the DNAs are of length N, and can be described by using all

  • 【华为OJ】【081-查找两个字符串a,b中的最长公共子串】

    题目描述 查找两个字符串a,b中的最长公共子串 输入描述 输入两个字符串 输出描述 返回重复出现的字符 输入例子 abcdefghijklmnop abcsafjklmnopqrstuvw 输出例子 jklmnop 算法实现 import java.util.Scanner; /** * Author: 王俊超 * Date: 2016-01-04 08:43 * Declaration: All Rights Reserved !!! */ public class Main { public

最新文章
  • 关于 Rails 的几则消息(2012-01-21)

    Rails 3.2 发布 http://weblog.rubyonrails.org/2012/1/20/rails-3-2-0-faster-dev-mode-routing-explain-queries-tagged-logger-store Agile Web Development with Rails (4th edition) 最新电子版已经更新到 Rails 3.2 http://pragprog.com/book/rails4/agile-web-development-wit

  • 什么面料的太阳伞防晒效果好 什么面料的太阳伞防晒效果好

    什么面料的太阳伞防晒效果好 本站生活常识配图 1.银胶涂层面料 银胶布面料不仅防紫外线效果好,而且价格相对便宜.使用的时候要注意银胶涂层不要淋雨,雨水会损伤伞的涂层,降低防晒效果.使用时间长的伞,银胶涂层会老化发黑,有时候你可以发现涂层出现一条条的印记,这是因为气候干燥涂层收缩了,需要更换新伞才能保证防晒效果. 2.两种新型面料 TC色织布面料是一种新型面料,可以水洗,不影响防晒效果.透光率不高,对波长380.300.220纳米的紫外线基本可以完全阻断.紫外线250-400纳米波段最容易引起人皮

  • iPhone/iPad越狱是什么意思? iPhone/iPad越狱是什么意思?

    [越狱是什么意思 ] 越狱(Jailbreak)是通过黑客团队制作和发布的越狱工具,利用系统漏洞将iPhone/iPad设备中的操作权限做出更改,突破苹果官方的限制,比喻的说,就是利用第三方工具逃出苹果为设备设置的"监狱". [越狱有什么用] 在越狱之后,玩家可以不使用iTunes来管理iPhone/iPad,而使用第三方软件.另外还可以安装很多在iTunes中没有的软件,比如输入法.喜欢个性化的网友还可以给iPhone更换字体,把界面改成其他样子. 如果玩家不越狱,这些都不可能实现.

  • 死神漫画恢复连载进入终章 火影忍者启用新OP 死神漫画恢复连载进入终章 火影忍者启用新OP

    据JUMP杂志消息,久保带人的人气漫画<死神>在7月宣布休载6周,现在休假结束,<死神>将按照此前计划的那样,从下期开始恢复连载,并将进入最终决战剧情"千年血战篇诀别谭",看起来本作离完结也不远了. 另据日媒消息,JUMP另一部看板漫画,岸本齐史<火影忍者>的TV动画版<火影忍者疾风传>(东京电视台系列播出)公开了新OP情报.从2013年10月开始,将启用日本人气偶像组合乃木坂46的新歌作为主题歌,歌曲名未定. 图为乃木坂46成员西野七瀬

  • 2015年公司尾牙活动策划方案

    公司从成立以来已经慢慢走向正轨,在传统佳节即将来临之 际,通过举办公司年会,总结一年来的成绩与不足,在年会上向员工传达下一年的工作目标及战略思想. 通过年会的活动,为员工提供一个展示自我的平台,拉近上下级之间的沟通,增强企业凝聚力,促进良好企业文化的形成. 一. 尾牙活动地点: _____________________________________; 尾牙活动时间:2013年1月x日 ____:__--____:__ 时; 其中:晚宴时间:____:__--____:__ 时; 晚会时间:_

  • 使用Xtrabackup备份MySQL数据库的教程

    可能大家对于这个工具有所了解了,Xtrabackup是一个对InnoDB做数据备份的工具,支持在线热备份(备份时不影响数据读写),下面一起来看看使用Xtrabackup备份MySQL数据库的教程 一.mysql的备份无非有下面几种方式 1.mysqldump工具 MySQL自己提供的mysqldump是把数据转换为SQL语句,这种方式的效率比较低,备份和还原的速度都很慢,而且在dump过程中为了保证数据一致性,任何数据插入和更新操作都会被挂起. 2.mysqlhotcopy工具 MySQL自己提

  • BaseAdapter以致notifyDataSetChanged()无效的三个原因及处理方法

    BaseAdapter导致notifyDataSetChanged()无效的三个原因及处理方法 前一段时间在做一个项目的时候遇到了一个关于BaseAdapter的notifyDataSetChanged()方法无效问题,当时在网上搜了一个解决方法,今天又遇到了一个类似的问题,我在这里做个记录,防止以后再次发生,或者其他朋友再次遇到. 一.ScrollView中嵌套ListView或GridView 原因:两个的滚动监听冲突 解决方法:重写ListView或GridView package com

  • 类的union成员,及其初始化解决方案

    类的union成员,及其初始化 我想做一个物理引擎,里面要有各种形状. 由于奇怪的原因,我不能把形状做成不同的派生类,所以把这些类型都揉到一起. 结果我发现,不知道怎么初始化一个union成员? C/C++ code // 先考虑两个最容易的形状 typedef enum { SHAPE_SPHERE, SHAPE_BOX } ShapeType; // 球的数据 typedef struct { float radius; } SphereData; // 长方块的数据 struct { fl

  • 《饥荒》DLC触手怪BOSS无伤打法视频攻略

    饥荒游戏中有许多BOSS,那么这些BOSS该要如何来无伤击杀呢?下面小编给各位玩家带来了关于本作中DLC触手怪BOSS无伤打法视频攻略,快来看看吧. 饥荒新手攻略 食谱大全 BOSS打法 安家位置 联机教程 全人物详解 各季节必备物品 武器装备介绍 快速砍树方法 查看版本方法 所有材料介绍 饥荒热门攻略 击杀生物宝典 利用巨鹿方法 洞穴怪物详解 冒险速通攻略 脑残值补充方法 陷阱布置技巧 牦牛详细介绍 坎普斯背包出处 危险生物排名 新手百日入门 正版资料整理 装备道具汇总 蜘蛛巢穴养殖心得 存档

  • 自己写的控制台版三国杀,该怎么处理

    自己写的控制台版三国杀 控制台三国杀的说明 这个程序耗费了我三四个星期的时间与精力,不过做的很粗糙,没有实现三国杀的全部功能. 现在这个版本,实现的功能是两个武将一对一,玩家开始时控制A武将,由电脑接管B武将来响应A的出牌:A武将回合 结束后,玩家控制B武将,由电脑接管A武将响应B武将出牌.(不要喷我哦~现在没实现AI控制主动出牌~)如此循环往复,直 到一名武将阵亡,游戏宣告结束. 这个程序使用三国杀标准包,一共104张牌.实现了杀.闪.桃.乐不思蜀.闪电.无中生有.南蛮入侵.万箭齐发 .桃园结

热门推荐
  • 微软Surface Hub交付:巨型平板的春天 微软Surface Hub交付:巨型平板的春天 微软的巨屏Surface Hub开始交付了,虽然微软两次推迟Surface Hub的发售,但是近期微软开始正式的想企业用户交付Surface Hub这一巨型平板. 据悉,微软在去年的一月份正式发布了Surface Hub,表示这款产品从7月1日开始接受预定,将在2015年9月1日进行发售,但是发售时间最终被延期到2016年的1月1日,这是微软的第一次跳票. 但是,到了2016的1月1日之前,微软表示将再次延期,到2016年的第一季度,同时全系涨价2000美元. 而这一次,微软履行 它的承诺向企业
  • 宇宙探秘:月球和火星暗竟出现八个外星人基地! 宇宙探秘:月球和火星暗竟出现八个外星人基地! 一种阴谋论观点认为,人类所有"载人登月任务"在30年前突然中止,是出于对在月球上存在的外星力量的恐惧.据称,在月球与火星上,总共有八个外星人基地存在. 1号基地 信息接收时间:1997年8月13日 [位置]:从地球上看,就在左边,仍有一些光线.基地是联系在一起的.不需要任何地下通道,好像它们可以自由移动,都不需要隐藏.#1不见得很很重要,这是我的发现. [用途]:航空港 接收不同类型的宇宙飞船,这意味着它们也能够从这里起飞.这里的飞船都是预备作长途旅行的,就像我们的国际机场一样.它们可
  • LOL新英雄海妖祭司曝光 触手鞭笞的女英雄 LOL新英雄海妖祭司曝光 触手鞭笞的女英雄 LOL美服今日公布了一位全新的英雄.这名新英雄似乎与比尔吉沃特和暗影岛有着不一般的联系,但要说最为特别的就是她的能力了.illaol(暂译为:俄洛伊)是一名女祭司,她能够操控一种奇怪的力量,但没有人知道她的力量究竟从何而来. [英雄技能] 被动技能:古神预言 伊洛依在附近的墙周期性地刷新出一个触手.触手会与伊洛依的技能和最近被击杀的单位发生互动,否则会静止一分钟. Q技能:触手鞭笞 被动:触手击中敌方英雄可以为伊洛依回复一小部分已损失的生命值. 主动:伊洛依召唤出一个触手猛击目标方向,对所有命中
  • LIGO证实爱因斯坦引力波 相对论中黑洞理论揭秘 LIGO证实爱因斯坦引力波 相对论中黑洞理论揭秘 爱因斯坦被誉为超级天才,他提出的广义相对论还有狭义相对论至今对后世依然影响深重,近期,相对论中提出的引力波一次又称为人们关注的焦点,因为LIGO终于对引力波的存在进行了证实,我们来一起了解一下详情吧. 在<三体>和<星际穿越>等著名科幻作品中,引力波都是极重要的"角色",也是爱因斯坦相对论的最伟大预言,如今被证实.人类的好奇心,以及我们未知的宇宙,岂止星辰大海. 在中国人最愉快喜庆的春节,美国科学家们宣布了科学界重大发现."我们成功检测了引力波!&qu