poj 2774 最长公共子--弦hash或后缀数组或后缀自己主动机

http://poj.org/problem?id=2774

我想看看这里的后缀数组：http://blog.csdn.net/u011026968/article/details/22801015

本文主要讲下怎么hash去找

開始的时候写的是O(n^2 logn)算法果断超时。

。。尽管也用了二分的。。

代码例如以下：

//hash+二分

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <cmath>

#include <map>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdin)

const ull B = 31;    /*according to the book*/

const int MAXN = 100000+100;

char a[MAXN],b[MAXN],tmp[MAXN];

int n,m;

ull ah[MAXN];

int C(int len)

{

    int pos=m-len+1;

    ull t=1,ah=0,bh=0,tmp;

    for(int i=0;i<len;i++)

    {

        t*=B;

        ah=ah*B+a[i];

    }

    tmp=ah;

    for(int k=0;k<pos;k++)///////

    {

        bh=0;

        ah=tmp;

        for(int i=k;i<k+len;i++)

            bh=bh*B+b[i];

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

        {

            if(len==27)

            {

                printf("#k=%d# i=%d ah bh ",k,i);

                cout << ah << ' ' << bh << endl;

            }

            if(ah==bh)

            {

                //printf("#k=%d# size=%d %s\n",k,strlen(b+k),b+k);

                return 1;

            }

            if(i+len<n)ah=ah*B+a[i+len]-a[i]*t;

        }

    }

    return 0;

}

int solve()

{

    n=strlen(a),m=strlen(b);// a--long b-short

    if(n<m)

    {

        swap(n,m);

        strcpy(tmp,a);

        strcpy(a,b);

        strcpy(b,tmp);

    }

    int d=0,up=m+1,mid;

    while(up>d+1)

    {

        mid=(d+up)/2;

        if(C(mid))d=mid;

        else up=mid;

    }

    return d;

}

int main()

{

    IN("poj2774.txt");

    while(~scanf("%s%s",a,b))

    {

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

    }

    return 0;

}

然后參考了队友的写法，改为这么写：

1、预处理出base数组；

2、将test文本串处理，长为len的哈希值存下来。然后排序，

3、计算第一个场为len的模式串的哈希值，每次更新都是O(1)操作了，然后二分查找

这道题写的时候的问题主要还是自己写的下标把自己弄迷糊了，begin=k，那么begin+len指向结尾字符的下一个字符

//hash+二分

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <cmath>

#include <map>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdin)

const ull B = 1e8+7;    /*according to the book*/

const int MAXN = 100000+100;

char a[MAXN],b[MAXN],tmp[MAXN];

int n,m;

ull ah[MAXN],base[MAXN];

int C(int len)

{

    int pos=m-len+1;

    ull bh=0,tmp=0;

    for(int i=0;i<len;i++)

        tmp=tmp*B+a[i];

    ah[0]=tmp;

    for(int i=0;i+len<=n;i++)/////////

        ah[i+1]=ah[i]*B+a[i+len]-a[i]*base[len];

    sort(ah,ah+n-len+1);

    for(int i=0;i<len;i++)

        bh=bh*B+b[i];

    for(int k=0;k<pos;k++)

    {

        if(binary_search(ah,ah+n-len+1,bh))

        {

            return 1;

        }

        bh=bh*B+b[k+len]-b[k]*base[len];

    }

    return 0;

}

int solve()

{

    n=strlen(a),m=strlen(b);// a--long b-short

    if(n<m)

    {

        swap(n,m);

        strcpy(tmp,a);

        strcpy(a,b);

        strcpy(b,tmp);

    }

    int d=0,up=m+1,mid;

    while(up>d+1)

    {

        mid=(d+up)/2;

        if(C(mid))d=mid;

        else up=mid;

    }

    return d;

}

int main()

{

    //IN("poj2774.txt");

    base[0]=1;

    for(int i=1;i<MAXN;i++)

        base[i]=base[i-1]*B;

    while(~scanf("%s%s",a,b))

    {

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

    }

    return 0;

}