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=1000000007;
const qword _a=29;
qword hs1[MAXN],hs2[MAXN];
qword pow_mod(qword a,int x)
{
        qword ret=1;
        while (x)
        {
                if (x&1)ret=ret*a%mod;
                a=a*a%mod;
                x>>=1;
        }
        return ret;
}

inline qword hash1(int x,int y)
{
        return ((hs1[y]-hs1[x-1]*pow_mod(_a,y-x+1))%mod+mod)%mod;
}
inline qword  hash2(int x,int y)
{
        return ((hs2[y]-hs2[x-1]*pow_mod(_a,y-x+1))%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=-1;
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[2][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
%s",str[0]+1,str[1]+1);
        int n=strlen(str[0]+1),m=strlen(str[1]+1);
        int l=0,r=min(n,m)+1;
        int mid;
        hs1[0]=hs2[0]=1;
        for (i=1;i<=n;i++)
                hs1[i]=((qword)hs1[i-1]*_a%mod+str[0][i]-'a'+1)%mod;
        for (i=1;i<=m;i++)
                hs2[i]=((qword)hs2[i-1]*_a%mod+str[1][i]-'a'+1)%mod;
        //cout<<hash1(1,2)<<endl;;
        bool flag;
        int ansp;
        while (l+1<r)
        {
                memset(V1,0,sizeof(V1));
                memset(V2,0,sizeof(V2));
                flag=false;
                mid=(l+r)>>1;
                tope=-1;
            //    mid=8;
                for (i=1;i+mid-1<=n;i++)
                {
                        y=i+mid-1;
                        x=i;
                        z=hash1(x,y);
                        addedge(V1,z%VAL1,x);
                        addedge(V2,z%VAL2,x);
                //        cout<<z<<endl;
                }
                for (i=1;i+mid-1<=m;i++)
                {
                        y=i+mid-1;
                        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[1][l+ansp]=0;
        printf("%s
%d
",str[1]+ansp,l);
        return 0;
}