首页 > 代码库 > POJ 2774 哈希+二分长度

POJ 2774 哈希+二分长度

思路:这题一看就知道是后缀数组做的了,好像以前做过,不过现在专攻哈希,所以就用哈希做了。

不过这题我真是要疯了!!!

刚开始写的就对了,然后二分while循环那忘了写等号了,然后一直WA,尼玛,然后自己居然给出一组样例:

bbaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaa

这组的样例中的长度为6和7的时候哈希值居然不一样,然后输出了6;然后逗B的以为哈希是有bug的,然后改来改去,把哈希种子改成:131,1313,13131,131313,1313131,13131313,131313131,1313131313,100000007,都不行;又改了哈希的做法,依然狂WA不止。然后用了别人博客的哈希方法测了一下,发现这组例子居然答案也是6,这下就发现了自己二分的错了……搞了一晚上,错在细节上了,晕!!!!!!!!!!!!!!!!!!!!!!!!!!

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 100105
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ull base[maxn],seed=131,one[maxn],aa[maxn];
char s[maxn],str[maxn];
int len1,len2;
bool judge(int n)
{
    int i;
    aa[0]=0;
    for(i=1;i<=n;i++)
        aa[i]=aa[i-1]*seed+s[i-1]-'a'+1;
    one[0]=aa[i-1];
    int k=1;
    for(;i<=len1;i++)
    {
        aa[i]=aa[i-1]*seed+s[i-1]-'a'+1;
        one[k++]=aa[i]-aa[i-n]*base[n];
    }
    sort(one,one+k);
    for(int j=0;j<k;j++)
        cout<<one[j]<<' ';
    cout<<endl;
    aa[0]=0;
    for(i=1;i<=n;i++)
        aa[i]=aa[i-1]*seed+str[i-1]-'a'+1;
    ull bb=aa[i-1]-aa[i-1-n]*base[n];
    if(binary_search(one,one+k,bb)) return true;
    for(;i<=len2;i++)
    {
        aa[i]=aa[i-1]*seed+str[i-1]-'a'+1;
        bb=aa[i]-aa[i-n]*base[n];
        if(binary_search(one,one+k,bb)) return true;
    }
    return false;
}
int main()
{
    //freopen("1.txt","r",stdin);
    base[0]=1;
    for(int i=1;i<maxn;i++)
        base[i]=base[i-1]*seed;
    scanf("%s%s",s,str);
    len1=strlen(s),len2=strlen(str);
    int l=0,r=min(len1,len2)+1,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(judge(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}


POJ 2774 哈希+二分长度