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、首先将所有的字符串每读取一个,就将其反转,作为一组,假设其下标为i到j,那么cnt[i]到cnt[j]都标记为一个数字(这个数字意思是第几个读入的字符串)

2、注意将字符串及其反串用一个未出现的字符隔开,我用的‘\0‘

3、二分答案,二分判断是不是合法的函数我折腾了很久...

lcp的时候  一个非常容易错的地方---不要把你加的空字符也算上

    for(int i=0;i<n;i++)
    {
        int j=sa[rk[i]-1];
        if(h>0)h--;
        for(;j+h<n && i+h <n;h++)
            if(s[j+h]!=s[i+h] || (s[j+h] == '\0' && s[i+h] == '\0'))break;/*****此处注意排除分隔符******/
        lcp[rk[i]-1]=h;
    }

最终是这么写的:

int C(int x)
{
    memset(sea,0,sizeof(sea));
    int num=0,ret=0,last=0;
    for(int i=ns*2;i<n;i++)//<span style="font-family: Arial, Helvetica, sans-serif;">i=ns*2,因为开始ns*2-1个都是空字符</span>
    {
        if(lcp[i]>=x)  //lcp的定义好好看看,里面的后缀本身就是按字典序的,所以<span style="font-family: Arial, Helvetica, sans-serif;">lcp[i]>=x能保证连着的这几个后缀的公共前缀相同</span>
        {
            sea[cnt[sa[i]]]=sea[cnt[sa[i+1]]]=1;
        }
        else<span style="white-space:pre">	</span>//看是不是合法,不合法就重新计数
        {
            for(int i=0;i<=ns;i++)
                if(sea[i])ret++;
            if(ret>=ns)
            {
                return 1;
            }
            else ret=0;
            memset(sea,0,sizeof(sea));
        }
    }
    for(int i=0;i<=ns;i++)
        if(sea[i])ret++;
    if(ret>=ns)return 1;
    else return 0;
}

做这题花了很久,但是基本没参考题解,基本完全是自己做的,感觉不错

学到了:

1、读取s将s反转存到同一个数组里,写法还是蛮锻炼代码能力的

2、C的写法-------因为后缀数组+lcp+二分非常广泛,

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

const int  MAXN =20200;

using namespace std;

int n,k,alen,rkcnt,ns;//n=strlen(s);
int rk[MAXN],tmp[MAXN],sa[MAXN],lcp[MAXN],cnt[MAXN],sea[120];//rank为c++的保留字,所以rk代之,cnt记录术语第几个
char s[MAXN];
char str[101][101];

bool cmpSa(int i,int j)
{
    if(rk[i] != rk[j])return rk[i]<rk[j];
    else
    {
        int ri = i+k<=n?rk[i+k]:-1;
        int rj = j+k<=n?rk[j+k]:-1;
        return ri<rj;
    }
}

void construct_sa()
{
    //n=strlen(s);
    for(int i=0;i<=n;i++)
    {
        sa[i]=i;
        rk[i]=i<n?s[i]:-1;
    }
    for(k=1;k<=n;k*=2)
    {
        sort(sa,sa+n+1,cmpSa);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+(cmpSa(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++)
            rk[i]=tmp[i];
    }
}

void construct_lcp()
{
    for(int i=0;i<=n;i++)rk[sa[i]]=i;
    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++)
    {
        int j=sa[rk[i]-1];
        if(h>0)h--;
        for(;j+h<n && i+h <n;h++)
            if(s[j+h]!=s[i+h] || (s[j+h] == '\0' && s[i+h] == '\0'))break;/*****此处注意排除分隔符******/
        lcp[rk[i]-1]=h;
    }
}

int C(int x)
{
    memset(sea,0,sizeof(sea));
    int num=0,ret=0,last=0;
    for(int i=ns*2;i<n;i++)
    {
        if(lcp[i]>=x)
        {
            sea[cnt[sa[i]]]=sea[cnt[sa[i+1]]]=1;
        }
        else
        {
            for(int i=0;i<=ns;i++)
                if(sea[i])ret++;
            if(ret>=ns)
            {
                return 1;
            }
            else ret=0;
            memset(sea,0,sizeof(sea));
        }
    }
    for(int i=0;i<=ns;i++)
        if(sea[i])ret++;
    if(ret>=ns)return 1;
    else return 0;
}

int main()
{
    //freopen("hdu 1238.txt","r",stdin);
    int ncase,len,ii,j,maxlen;
    scanf("%d",&ncase);
    while(ncase--)
    {
        alen=len=maxlen=rkcnt=0;
        scanf("%d",&ns);
        for(int i=0;i<ns;i++)
        {
            scanf("%s",s+alen);
            len=strlen(s+alen);
            maxlen=max(maxlen,len);
            len++;
            alen+=len;
            for(j=alen,ii=alen-2;ii>=0 && s[ii];j++,ii--)
            {
                s[j]=s[ii];
            }

            s[j]=s[ii]='\0';
            alen+=len;
        }
        alen--;
        s[alen]='\0';
        int flag=0;
        for(int i=0;i<=alen;i++)
        {
            cnt[i]=rkcnt;
            if(!s[i])
            {
                flag=!flag;
                if(!flag)rkcnt++;
            }
        }
        n=alen;
        construct_sa();
        construct_lcp();
        int d=0,up=101,mid=101;    /*二分上限的选取*/
        while(up>1+d)
        {
            mid=(up+d)/2;
            if(C(mid))d=mid;
            else up=mid;
        }

        printf("%d\n",d);
    }

    return 0;
}

随后我会对后缀数组结合自己的做题还有国家集训队论文写个总结

poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津预选题,布布扣,bubuko.com

时间: 05-19

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

两个字符串的最长公共子串

import java.util.Scanner; /* 求两个字符串的最长公共子串*/ public class stringDemo {     public static void main(String[] args){      Scanner scanner = new Scanner(System.in);      System.out.println("请输入第一个字符串:");      String str1 = scanner.nextLine();     

求最长公共子串(串)

题目描述 求采用顺序结构存储的串s和串t的一个最长公共子串,若没有则输出false,若最长的有多个则输出最先出现的那一串. 输入要求 输入两个字符串 输出要求 输出公共子串 假如输入 abcdef adbcef 应当输出 bc 思路: 1. 将连个字符串分别以行列组成一个矩阵. 2.若该矩阵的节点对应的字符相同,则该节点值为1. 3.当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1,这样当前节点的值就是最大公用子串的长. (s2) b c d e (s1) a        

求最长公共子串

poj2774,codevs3160 题目描述 Description 给出两个由小写字母组成的字符串,求它们的最长公共子串的长度. 输入描述 Input Description 读入两个字符串 输出描述 Output Description 输出最长公共子串的长度 样例输入 Sample Input yeshowmuchiloveyoumydearmotherreallyicannotbelieveityeaphowmuchiloveyoumydearmother 样例输出 Sample Ou

POJ 1226后缀数组:求出现或反转后出现在每个字符串中的最长子串

思路:这题是论文里的最后一道练习题了,不过最后一题竟然挺水的. 因为求的是未反转或者反转后,最长公共子串. 刚开始还真不知道怎么构建连接成一个字符串,因为需要有反转嘛! 但是其实挺简单的,把未反转的和反转后的字符串都连起来,中间用未出现过的字符隔开就行了!然后未反转的和反转的在同一组. 二分枚举最长的公共前缀长度,然后统计看看这个最长的长度在不在所有的组里,如果在就符合-- #include<iostream> #include<cstdio> #include<cstrin

hdu 1238 Substrings (暴搜,枚举)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1238 Substrings Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8391    Accepted Submission(s): 3862 Problem Description You are given a number of

字符串hash + 二分答案 - 求最长公共子串 --- poj 2774

Long Long Message Problem's Link:http://poj.org/problem?id=2774 Mean: 求两个字符串的最长公共子串的长度. analyse: 前面在学习后缀数组的时候已经做过一遍了,但是现在主攻字符串hash,再用字符串hash写一遍. 这题的思路是这样的: 1)取较短的串的长度作为high,然后二分答案(每次判断长度为mid=(low+high)>>1是否存在,如果存在就增加下界:不存在就缩小上界): 2)主要是对答案的判断(judge函数

POJ 1080 Human Gene Functions(求两字符串相似度:LCS变形)

POJ 1080 Human Gene Functions(求两字符串相似度:LCS变形) http://poj.org/problem?id=1080 题意: HDU1080 给你两个由字符A,C,G,T构造的字符串s1和s2, 现在你可以在这两个字符串中插入空格, 使得两串长相等(但是不能使得s1的空格对应s2的空格位置). 然后给你s1的特定字符对应s2中特定字符所能获得的分数矩阵: 问你最后两个字符串所能获得的最大分数是多少? 分析: 本题很类似于求字符串最短编辑距离或者求字符串LCS的

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

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

后缀数组(多个字符串的最长公共子串)—— POJ 3294

对应POJ 题目:点击打开链接 Life Forms Time Limit:6666MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Submit Status Description Problem C: Life Forms You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial tra