Contest 20140914 Mushroom写情书字符串雙hash 後綴數組

0111:Mushroom写情书

查看
提交
统计
提问

总时间限制:: 10000ms
内存限制:: 256000kB

描述

有一天，Mushroom准备向他的GF表白，为了增加表白成功率，Mushroom写了封情书寄给他的GF（记为S1），而他的GF也回寄了一封（记为S2）。现在，Mushroom想知道，这两封信的最长公共子串是多少。

输入

两行仅包含小写字母的字符串（S1，S2）。

输出

当不存在公共字符串时，输出一行0,。否则先输出一行表示最长公共子串，再输出最长公共子串的长度，如果有多个解满足，输出首先在S2中出现的（详见样例）

样例输入

abcdef

defabc

样例输出

def

3

//	abc和def都在S1和S2中出现过，由于def在S2中先出现，所以输出def

提示

对于30%的数据，1<=|S2|<=|S2|<=100
对于60%的数据，1<=|S2|<=|S2|<=1000
对于100%的数据，1<=|S2|<=|S2|<=250000

来源

mushroom

在做這道題之前還重來沒有編過雙hash，這次算是找了一下感覺，反正自己覺得雙hash非常容易些錯，所以以後要多加小心。

考場上我用的後綴數組，由於題目中要求優先在s2中出現，所以後綴數組顯得非常麻煩。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

#include<stack>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 251000

#define MAXM 251000

#define MAXE MAXN

#define VAL1 100007

#define VAL2 1000007

#define PROB "letter"

typedef long long qword;

const qword mod=;

const qword _a=;

qword hs1[MAXN],hs2[MAXN];

qword pow_mod(qword a,int x)

{

        qword ret=;

        while (x)

        {

                if (x&)ret=ret*a%mod;

                a=a*a%mod;

                x>>=;

        }

        return ret;

}

inline qword hash1(int x,int y)

{

        return ((hs1[y]-hs1[x-]*pow_mod(_a,y-x+))%mod+mod)%mod;

}

inline qword  hash2(int x,int y)

{

        return ((hs2[y]-hs2[x-]*pow_mod(_a,y-x+))%mod+mod)%mod;

}

/*

struct aaa

{

        short s[MAXN];

        char ss[MAXN];

        int v[MAXN];

        void Init(char *_ss)

        {

                strcpy(ss,_ss);

                n=strlen(ss);

                m=n;

                int i;

                for (i=0;i<n;i++)

                {

                        s[i]=ss[i]-'a'+2;

                }

                v[0]=1;

                for (i=1;i<n;i++)

                {

                        v[i]=(v[i-1]*_a+s[i])%mod;

                }

        }

};*/

struct Edge

{

        int pos;

        Edge *next;

}E[MAXE],*V1[VAL1],*V2[VAL2];

int tope=-;

void addedge(Edge **V,int x,int y)

{

        E[++tope].pos=y;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

bool cross(Edge *ne1,Edge *ne2)

{

        Edge *ne3,*ne4;

        for (ne3=ne1;ne3;ne3=ne3->next)

        {

                for (ne4=ne2;ne4;ne4=ne4->next)

                {

                        if (ne3->pos==ne4->pos)return true;

                }

        }

        return false;

}

char str[][MAXN];

int main()

{

        freopen(PROB".in","r",stdin);

        freopen(PROB".out","w",stdout);

        //freopen(PROB".out","w",stdout);

        int i,j,k;

        int x,y,z;

        scanf("%s\n%s",str[]+,str[]+);

        int n=strlen(str[]+),m=strlen(str[]+);

        int l=,r=min(n,m)+;

        int mid;

        hs1[]=hs2[]=;

        for (i=;i<=n;i++)

                hs1[i]=((qword)hs1[i-]*_a%mod+str[][i]-'a'+)%mod;

        for (i=;i<=m;i++)

                hs2[i]=((qword)hs2[i-]*_a%mod+str[][i]-'a'+)%mod;

        //cout<<hash1(1,2)<<endl;;

        bool flag;

        int ansp;

        while (l+<r)

        {

                memset(V1,,sizeof(V1));

                memset(V2,,sizeof(V2));

                flag=false;

                mid=(l+r)>>;

                tope=-;

            //    mid=8;

                for (i=;i+mid-<=n;i++)

                {

                        y=i+mid-;

                        x=i;

                        z=hash1(x,y);

                        addedge(V1,z%VAL1,x);

                        addedge(V2,z%VAL2,x);

                //        cout<<z<<endl;

                }

                for (i=;i+mid-<=m;i++)

                {

                        y=i+mid-;

                        x=i;

                        z=hash2(x,y);

                        if (V1[z%VAL1] && V2[z%VAL2] && cross(V1[z%VAL1],V2[z%VAL2]))

                        {

                                flag=true;

                                ansp=i;

                                break;

                        }

                //        cout<<"#"<<z<<endl;

                }

                if (flag)

                        l=mid;

                else

                        r=mid;

        }

        str[][l+ansp]=;

        printf("%s\n%d\n",str[]+ansp,l);

        return ;

}

S2

Contest 20140914 Mushroom写情书 字符串雙hash 後綴數組

0111:Mushroom写情书

Contest 20140914 Mushroom写情书字符串雙hash 後綴數組