这题思路其实很简单啦……
用hash做啦做啦做啦做啦~~~
对于每一个字符串~从前往后,依次算出前i 个字符的总的hash值,存到对应数组的i位置~
然后Q的时候比较第a 个和第b 个的前多少位是一样滴~输出就行啦啦啦啦啦~~
说一下我的悲剧:
1、 我特么以为是从a 号位置到b 号位置的所有字符串啊啊啊啊啊啊!!!TLE 了啊有木有!!!
2、我特么用的二维数组啊!!!二维数组啊!!!CE啊有木有有木有!!!根本开不了那么大的啊!!!
3、我特么HASH基数选得26啊!!!26啊!!!那特么的竟然是ASCLL码啊!!!要大于122啊有木有啊!!!WA了啊啊啊啊啊!!!
咳咳。。。回归。。。
第一个和第三个没什么好说的,第二个的解决方案就是改成用vector存储,不开一个固定大小的数组,而开动态数组,根据需要来添加所需的数字。
AC Memory: 0KB Time : 742MS
代码:
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<cmath> using namespace std; vector<unsigned long long> shash[100010]; int slen[100010]; char s[100010]; void solve(int pos) { int len=strlen(s); slen[pos]=len; shash[pos].clear(); shash[pos].push_back(0); for(int i=1;i<=len;i++) shash[pos].push_back(shash[pos][i-1]*2333+s[i-1]); } int main() { int T,n,M,k,a,b; scanf("%d",&T); for(int t=1;t<=T;++t) { printf("Case %d:\n",t); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",s); solve(i); } scanf("%d",&M); while(M--) { scanf("%d%d",&a,&b); int len=min(slen[a],slen[b]); int l=0,r=len; while(l<r) { int mid=(l+r+1)/2; if(shash[a][mid]==shash[b][mid]) l=mid; else r=mid-1; } printf("%d\n",l); } } return 0; }