首页 > 代码库 > 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 哈希+二分长度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。