首页 > 代码库 > poj 2774 最长公共子串--字符串hash或者后缀数组或者后缀自动机

poj 2774 最长公共子串--字符串hash或者后缀数组或者后缀自动机

2024-07-16 17:26:16   224人阅读

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;
}




联系
我们