位置:首页 » 技术 » 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

最新文章
  • 出Kindle4 啦

    年会抽奖中的,基本没有用... 到今天才进行第三次充电- - ¥400 (Kindle4 + 充电线) 到付 有意的Q吧:342868791 --cut-- freetstar在2012-04-30 21:59:3回答到: 这么便宜!... freetstar在2012-04-30 22:00:2回答到: @hxddh2010 hxddh2010在2012-04-30 22:04:5回答到: @freetstar 谢谢,很便宜啊,动摇了,有动心,我联系看看 dianso在2012-04-30 2

  • 内蒙古马鞍山国家森林公园

    马鞍山国家森林公园位于内蒙古赤峰市喀喇沁旗锦山镇东南5公里处,属喀喇沁王府的家庙,距赤峰市区 50公里,总面积24平方公里.辽代称此山为"马盂山",因马盂(鸡冠壶)与马鞍山形似,又称"马鞍山".随着当地旅游业的发展,又有"塞北小黄山"之美称.1993年被国家林业部批准为国家森林公园. 马鞍山环境幽雅,森林茂密,古松.奇峰.云海.清泉堪称"四绝"山峦叠翠,松涛阵阵,千年古松,挂于悬崖,立于谷中.巨石奇峰有40余座,其中"

  • AutoCAD三维建模教程:三通管的制作过程 AutoCAD三维建模教程:三通管的制作过程

    本系列AutoCAD三维建模教程由本站AutoCAD版块为对AutoCAD三维建模感兴趣的朋友整理制作的,是专为刚开始接触 AutoCAD三维的朋友定身打造的.本教程由浅入深,循序渐进,通过对60道练习题的绘制步骤讲解.各个三维命令的使用介绍,将喜爱AutoCAD三维 建模的朋友带进门.希望通过本教程的介绍,能给朋友们带来帮助. 更多教程和练习请点击这里,在这里有系列的教程.练习,并有老师对练习进行点 评与指导,欢迎朋友们的光临! 在学习中遇到问题可以到 论坛AutoCAD版块 发贴交流! 本例

  • 在版权娱乐公司的淫威之下 探秘私有BT网站 在版权娱乐公司的淫威之下 探秘私有BT网站

    在版权娱乐公司的淫威之下,海盗湾, TorrentSpy, MiniNova, Suprnova,BTChina等大批公开BT站点均已香消玉损.不过BT界的一批真猛士们则对此毫不在意,通过架设私有BT站点,他们照样可以上传和下载盗版多媒体文件,游戏和各种软件,而且几乎不会受到版权娱乐公司的骚扰,与公有BT站点不同,这些私有BT站点只有极少数熟客才可以进入.以下,就让我们进入这个相对陌生的世界,为大家揭开笼罩在私有BT站点头上的神秘面纱. 私有BT站点及其后盾简介: 私有BT站点的组织甚为严密,用

  • 2014感恩节老师祝福语大全

    2014感恩节老师祝福语大全 您是只小船,您是座小桥,送一代又一代人走向智慧的彼岸.啊!没有老师的帮助,我将在知识的海洋里失去前进的方向. 父母给了我躯体,您给了我灵魂.亲爱的老师,感恩节快快乐! 鸟儿遇到风雨,躲进它的巢里;我心上有风雨袭来时,总是躲在您的怀里--我的师长,您是我遮雨的伞,挡风的墙,我怎能不感谢您! 加减乘除,算不尽您作出的奉献!诗词歌赋,颂不完对您的崇敬!您用知识甘露,浇开我们理想的花朵;您用心灵清泉,润育我们情操的美果.今天是感恩节,在这不寻常的节曰里,献上我们深深的祝福!

  • 旅游卫视《最美中国》栏目拉开招商大幕 旅游卫视《最美中国》栏目拉开招商大幕

    零加盟费即可享受<最美中国>战略资源 11月2日,旅游卫视<最美中国>栏目在人民大会堂举行"旅游卫视旅游春晚 <最美中国>云南·弥勒篇 <最美中国>栏目全国加盟代理招商"新闻发布会,标志着<最美中国>经过一年的运行,正式步入了新的辉煌时代. <最美中国>制片人透露,旅游春晚是旅游卫视的年度盛会,2015年春晚将由<最美中国>栏目主办.世纪豪情(北京)演艺有限公司承办.香港盛烨堂国际投资集团.自由成功文化

  • 三星Note4快速充电是什么?GALAXY Note4快速充电功能介绍?(N9100) 三星Note4快速充电是什么?GALAXY Note4快速充电功能介绍?(N9100)

    GALAXY Note4快速充电功能是什么呢?Galaxy Note4支持快速充电功能,实现快速充电,需要注意以下几点 1.设备开启快速充电(设定-省电-快速充电 勾选). 2.手机屏幕关闭或手机关机的情况下可以实现快速充电. 3.使用Note4标配充电器 .

  • 教你用PS美化MM脸部 教你用PS美化MM脸部

    原图 原图和最终效果 1.打开原图,图层--调整--照片滤镜. 2.图层--调整--色彩平衡,分别从中间值.高光.暗调来调整蓝色. 3.所得的图像偏暗,我先调整一下曲线. 4.图层--调整--可选颜色,分别从红,蓝,白,中性色,黑色来调整得.数值如图所示: 最终效果图

  • 好手方家帮贴下好的免费空间?万谢!

    高手方家帮贴下好的免费空间?万谢!! 000webhost.com一概注册不了??用代理伪装成美国的ip也不行 现在还有好的免费空间吗? 高手方家帮贴下,万谢!! ------解决方案-------------------- http://www.webng.com/ ------解决方案-------------------- http://www.ggxx.com/

  • IntelliJ IDEA运用笔记

    IntelliJ IDEA使用笔记 习惯了用eclipse包括其中的各种快捷键,突然换一个IDE,各种快捷键习惯性地按下去然后出现各种不可理解的现象才反应过来,真的像要死过一次一样. 1. IDEA环境设置:File-Settings. 2. 和eclipse差别比较大的常用快捷键: 操作:IDEA || eclipse 删除行:Ctrl+Y || Ctrl+D 错误提示:Alt+Enter || Ctrl+1 进入声明:F3 || Ctrl+B 运行程序:Ctrl+F11 || Shift+F

热门推荐