位置:首页 » 技术 » LCP poj 2217 寻觅最长公共子串

LCP poj 2217 寻觅最长公共子串

日期:2014-03-31 阅读:0num
Advertisement

LCP poj 2217 寻找最长公共子串

题目:http://poj.org/problem?id=2217

首先解释,DP中的最长公共子序列和此处的最长公共子串区别-------------------序列可以是不连续的,但是子串是连续的

其次,LCP,lcp[i]就是lcp[rank[i]]和lcp[rank[i]+1]的最长公共前缀,那么把两个字符串接起来,然后找最长的lcp,就是答案

思路还是比较清晰的

上代码:

/*******************************************************/
//poj 2217 lcp+sa by Pilgrim
//最长公共子串---注意与动态规划的最长公共子序列不同
//2014.4.2
/******************************************************/

#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>

#define MAXN 10010
#define INF 0x80000000
//0x7fffffff
//0x80000000

using namespace std;

int n,k;//n=strlen(s);

int Rank[MAXN];
int tmp[MAXN];

/*使用Rank对sa排序*/
bool cmpSa(int i, int j)
{
    if(Rank[i] != Rank[j])return Rank[i] < Rank[j];
    else
    {   /*下面的Rank[t],已经是以t开头长度小于等于k/2的,
        sa[i]的名次,只是以i开头的后缀,而长度不同*/
        int ri = i+k <=n? Rank[i+k]:-1;
        int rj = j+k <= n ? Rank[j+k]:-1;
        return ri <rj;
    }
}

/*计算SA*/
void con_sa(char *s, int *sa)
{
    /*n=strlen(s);  必要时注明*/
    /*初始化sa和rank保证两点
        1、Rank[i]表示下标为i的是第几大,必须表示出相对大小,可以直接用字符代表其大小
        2、sa[1...n]值为1..n*/
    for(int i=0;i<=n;i++){
        sa[i]=i;Rank[i] = i < n?s[i]:-1;
    }

    /*利用长度为k的字符串对长度为2*k的字符串排序*/
    for(k=1;k<=n;k*=2)/*注意此代码中k是全局变量 别乱用,循环必须从1开始,因为0*2=0*/
    {
        sort(sa,sa+n+1,cmpSa);
        tmp[sa[0]] = 0; /*此时tmp只是暂存rank*/
        for(int i=1;i<=n;i++){
            tmp[sa[i]] = tmp[sa[i-1]] +(cmpSa(sa[i-1],sa[i])?1:0);
            /*这一句很关键,等号右侧的sa[i]在此循环里表示第i大的长度小于等于k/2的字符串,
              从而求出第i大的长度小于等于k的字符串的sa[i]*/
        }
        for(int i=0;i<=n;i++){
            Rank[i] = tmp[i];
        }
    }
}

void construct_lcp(char *s,int *sa,int *lcp)
{
    //n=strlen(s);
    for(int i=0; i<=n; i++)Rank[sa[i]]=i;

    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++)
    {
        int j=sa[Rank[i]-1];

        if(h>0)h--;
        for(; j+h<n && i+h<n; h++)
        {
            if(s[j+h]!=s[i+h])break;
        }
        lcp[Rank[i]-1]=h;
    }
}

int main()
{
    int sa[MAXN],lcp[MAXN];
    char s[MAXN],t[MAXN];
    char c;
    int ncase,mmax,len,leng;

    while(scanf("%d",&ncase)!=EOF)
    {
        while(ncase--)
        {
            mmax =0;
            while((c=getchar())==' '|| c=='\n');
            s[0]=c;
            int tt=1;
            while((c=getchar()) != '\n')
            {
                s[tt++]=c;

            }

            s[tt]='\0';
            while((c=getchar())==' '|| c=='\n');
            t[0]=c;
            tt=1;
            while((c=getchar()) != '\n')
            {
                 t[tt++]=c;

            }
            t[tt]='\0';
            len=strlen(s);
            leng =len+1+strlen(t);
            strcpy(s+len+1,t);
///////////////////////////////////////////////
//for(int i=0;i<leng;i++)
 //   putchar(s[i]);
//putchar('\n');
            n=leng;
            con_sa(s,sa);
            construct_lcp(s,sa,lcp);

           for(int i=0;i<leng;i++)
            {
              if((sa[i]<len) != (sa[i+1]<len))
                  mmax=max(mmax,lcp[i]);
            }
            printf("Nejdelsi spolecny retezec ma delku %d.\n",mmax);
        }
    }

    return 0;
}

LCP poj 2217 寻觅最长公共子串的相关内容

相关文章
  • 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 标题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 最长公共子串

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

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

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

  • POJ3294-Life Forms 后缀数组+2分答案 大于k个字符串的最长公共子串

    POJ3294--Life Forms 后缀数组+二分答案 大于k个字符串的最长公共子串 Life Forms Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 10800 Accepted: 2967 Description You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial t

  • 最长公共子串

    最长公共子串(Longest Common Substring)是一个非常经典的问题,它的基本描述为"给定两个字符串,求出它们之间最长的相同子字符串(要求连续)的长度".例如以下两个字符串S和T的的最长公共子串"howmuchiloveyoumydearmother",长度为27. S="yeshowmuchiloveyoumydearmotherreallyicannotbelieveit" T="yeaphowmuchiloveyo

  • 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

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

    求助 求最长公共子串 递归写的 程序运行不过 帮我看看哪里错误了 基本思想还是以前的求解方法:对于字符串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

最新文章
  • 薄荷招聘 Android 工程师

    我们是薄荷科技,即上海薄荷信息科技有限公司,是一家帮助女性健康生活.健康减肥的互联网公司.薄荷APP和薄荷网已拥有上千万用户,在APP STORE和安卓各大市场健康健美类应用中,均有不俗的成绩. 在这里,需求,实现,设计都是人人参与讨论 在这里,接触公司核心代码,有机会成长团队核心骨干 在这里,轻松自由,有机会尝试各种先进前沿的技术 在这里,工作环境舒适优雅,更有很多美女共事,男女比例1:2,没错,没有写反. 我们在寻找靠谱的Android工程师 职位描述及要求: 全日制本科及以上学历,2年左右

  • 资深Windows用户的10个习惯 资深Windows用户的10个习惯

    在笔者看来,判断一个Windows用户会不会"用"电脑,并非看他能否操作软件来工作或娱乐,而应该多注意一些他的操作细节,比如:能否避免一些低级的操作错误;能否利用一些系统小功能来提高工作效率;是否能在同样结果的前提下降低电脑的损耗;是否有足够强的安全意识--正是这些"细枝末节"才能让我们的电脑物尽其用,而不仅是一个摆设. 玩转系统!资深Windows用户的10个习惯 所以,无论你是一个大神级的资深用户或一个初来乍到的小白用户,下面的15个PC基本使用习惯和技巧是应该

  • 父母拍摄儿童成长的五个小技巧 父母拍摄儿童成长的五个小技巧

    为了迎接家庭的新成员--小baby的到来,新手爸妈大多都会买台相机,帮自家的宝贝记录下珍贵的成长点滴.这次,小编在这里为大家介绍五个小技巧,让你快速拍出宝贝的漂亮照片. TIPS1:制造情景 小朋友的很多行为都是让人意想不到的,但是有的时候是也是可预料的,比如说,把宝贝放在沙滩上,或者给他个巨大的棉花糖,又或者让他置身于某一情景之中,你猜他会有什么反应? EOS 5D Mark II 速度:1/250s 光圈:F1.8 ISO:200 焦距:85mm 趴在台子上等妈咪按快门,妈咪我好期待 EOS

  • 立冬是第几个节气 立冬是第几个节气

    立冬,是二十四节气中的第19个节气,也是汉族传统节日之一,在公历每年11月7-8日之间,迎接立冬的到来,立,建始也,表示冬季自此开始.冬是终了的意思,有农作物收割后要收藏起来的含意,中国又把立冬作为冬季的开始. 立冬与立春.立夏.立秋合称四立.古代社会中是个重要的节日.过去是个农耕社会,劳动了一年,利用立冬这一天要休息,顺便犒赏一家人的辛苦.谚语"立冬补冬,补嘴空"就是最好的比喻. 天文学上把"立冬"作为冬季的开始,按照气候学划分,我国要推迟20天左右才入冬.立冬时

  • 亚杰商会摇篮计划第11期创业者招募

    AAMA亚杰商会的"未来科技商业领袖摇篮计划"(简称"摇篮计划")是推动中国青年创业家成长与进步的公益项目,每一期邀请10余位科技.商业.投资金融界的精英作为导师,同时通过多种渠道以及严格机制甄选出20余位富有潜力的创业家,以一对一.一对多.多对一和多对多的深度辅导.培训.讲座和集体活动等多种方式,为年轻创业家创造面对面向导师学习.与其他年轻创业精英交流.分享.建立友谊的机会,打造出新型的网络化学习型组织. "摇篮计划"自2006年以来,已经成功

  • 肉丝炒桂粉的做法 肉丝炒桂粉的做法

    原料: 桂粉.瘦肉丝.胡萝卜丝.菜心.蒜沫.生抽老抽,油盐. 做法: 1.肉丝用淀粉.生抽腌好大火下少许蒜沫爆炒备用; 2.另起锅倒油先下蒜沫.胡萝卜丝翻炒待胡萝卜炒软倒入菜心一同加少许盐翻炒; 3.然后倒入桂粉.炒好的肉丝加适量盐不停翻炒均匀;http://www.3lian.com/ 4.加适量老抽上色调味加少许水不停翻炒均匀即可.

  • 卫浴装修 所不知道的8大环保原则

    卫浴装修环保家装还得遵循八大原则"没什么别没钱有什么别有病",而面对现如今的家装市场,加装后的健康问题恐怕是众多朋友关心的唯一话题,而究竟才能做到环保家装? 如何才能在家装后最好的实现健康?其实,这需要我们从家装本身做起,从选料,用料入手,这样才能实现环保家装,健康家装.今天,笔者就给大家带来了健康家装需要谨遵的八大原则,有家装准备的朋友不妨一起来了解下. 灯具不应过于花哨 在不定情况下,彩色光源会让人眼花缭乱,还会干扰大脑中枢神经,使人头晕目眩.恶心呕吐.失眠等.建议选柔和的节能灯,

  • 修改tomcat用户名和密码的方法详解

    为了方便远程管理tomcat我们可以给tomcat设置一个用户名和密码了,下面一起来看看具体的设置步骤,其实非常的简单在网上有很多相关的教程. 我们可以通过图形用户界面来管理tomcat,启动tomcat,在地址栏中输入: http://localhost:8080 就可以看见tomcat的欢迎页面,点击左边的tomcat manager 就会出现一个对话框,需要输入用户名和密码,当忘记最开始安装tomcat时的用户名和密码时,我们可以通过以下方杰来解决: 修改tomcat-users.xml文

  • 红米2A云相册怎么开启?红米2A开启云相册教程 红米2A云相册怎么开启?红米2A开启云相册教程

    红米手机2A是小米公司于2015年3月31日推出的新款机,为红米手机2的衍生机型了,下面我们来为各位介绍红米2A云相册怎么开启? 1)我们在红米手机界面点击[图库]因为我们要开启的功能就在图库中,进入到图库你会发现有一个云字,我们点击它就是[云相册]:(如下图) 2)在我们点击云之后就进入到手机的云相册界面上点击右上角[齿轮标志]之后我们再点击[启用云相册]即可:(如下图) 好了这样红米2A手机的去相册就开启成功了,这样备份 照片我们是需要wifi网络了,所以各位朋友上照片到云相册时最好选择有w

  • Servlet的API(2)

    Servlet的API(二) web服务器收到客户端的http请求,会针对每一次请求,分别创建一个用于代表请求的request对象和代表响应的response对象.request和response对象既然代表请求和响应,那我们获取客户机提交过来的数据,只需要找request对象即可,要向客户机输出数据,只需要找response对象即可.这一节我们来看看Servlet的这两个对象:HttpServletResponse对象和HttpServletRequest对象. 1. HttpServletR

热门推荐
  • 世界十大运河有哪些 世界十大运河有哪些 [世界十大运河] [1]京杭大运河[中国·1801km] [2]伊利运河[美国·581km] [3]苏伊士运河[埃及·173km] [4]阿尔贝特运河[比利时·130km] [5]莫斯科运河[俄罗斯·128km] [6]伏尔加河∽顿河运河[俄罗斯·101km] [7]基尔运河[德国·98.7km] [8]约塔运河[瑞典·87km] [9]巴拿马运河[巴拿马·81.3km] [10]曼彻斯特运河[英国·58km] 注:更多内容请关注本站百科栏目
  • 玉米的五种做法营养大PK 玉米的五种做法营养大PK 烤玉米,蒸玉米,煮玉米,玉米粥,玉米汤,这五种日常餐桌上出镜率较高的玉米食谱,并不是每种都推荐经常食用哦!不同身体状况的人对于玉米的烹调方式也有不同的要求. 玉米被称为"天下第一主食",吃法很多样,哪种吃法更值得推荐呢? 本站阅读配图 烤玉米:最不推荐. 明火温度过高,会破坏玉米的营养,同时,还可能生成一些致癌物质,尤其是路边卖的烤玉米,烤的时间一般都特别长,就更不健康了. 专家建议:烤玉米确实好吃,实在是贪这一口的人,建议改吃烤箱制作的玉米,因为烤箱温度.时间可自行设定,一般设置在1
  • win7麦克风侦听怎么设置 win7麦克风侦听怎么设置 win7系统中麦克风侦听要怎么设置. 1.右键单击右下角小喇叭图标,单击"声音"; 2.单击"录制"选项卡,单击"麦克风"图标,单击"属性"; 3.单击"侦听"选项卡,勾选"侦听此设备",应用即可.
  • 宇宙生命分子现身蛇夫座恒星周围   距地球400光年 宇宙生命分子现身蛇夫座恒星周围 距地球400光年 据国外媒体报道,近日一个天文学家小组在宇宙中发现的生命分子:乙醇醛,这是一种简单的糖分子.发现该生命分子的区域位于一颗年轻的双星系统中,其质量与我们太阳类似,科学家将其编号为IRAS 16293-2422.这是科学家第一次在宇宙空间中发现糖分子存在于恒星周围,这也意味着构建生命的基础模块处于正确的位置上,如果在适当的时间该恒星周围形成行星,那么就有可能促进生命的诞生. IRAS 16293-2422恒星距离我们大约400光年,位于比较靠近地球的恒星形成区中,这里是天文学家研究星际分子以及年轻恒星
  • 解决win8系统光驱无法识别光盘的解决方法 解决win8系统光驱无法识别光盘的解决方法 现如今只要带光驱的电脑用户,能够直接通过系统光盘安装电脑系统,不过在近期有部分用户发现win8系统出现无法识别dvd光盘的问题,无法识别dvd光盘也就意味着我们无法通过光盘进行安装相应的游戏软件或读取dvd中的内容,通常情况下解决该问题我们会对相应光驱驱动进行重装,不过如果使用该方法也无法解决光驱无法识别dvd光盘的问题怎么办呢?故此小编为大家带来了另外一种解决方法,希望对您有所帮助! 解决win8系统光驱无法识别光盘的解决方法 第一步:首相我们需要打开注册表,可通过Win+R组合键打开运行框,