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