這兩題比賽做的時候各種卡，太久沒有寫過這種類型的題目了。各種細節(jié)想不清楚。 賽后看下網(wǎng)上大部分題解的代碼，發(fā)現(xiàn)大部分都是直接用TRIE+暴力直接搞的--!，隨便找了份代碼發(fā)現(xiàn)有些數(shù)據(jù)這種做法是超時的，比如n=m=1,然后下面兩行長度為100000的全為a的字符串。明顯直接暴力DFS復(fù)雜度為n*n.

比賽的時候，還想用26*100000*log(n)然后用STL來去重復(fù)，結(jié)果直接超時果真STL還是太耗時了。。。

1260解法：

因為字符串集合S中N個字符串是兩兩不同的（這點比較關(guān)鍵，利用這點可以減少代碼量），所以對S中得N個字符進行HASH處理（可以只得到HASH值不建HASH表，查詢時候用二分）。然后對于需要查詢的M個字符串，因為這M個字符串總長是10^5，所以在每個字符串每一位暴力插入（‘a(chǎn)’-‘z’）,也就是要枚舉26*10^5種情況，用一次預(yù)處理可以使得每次HASH操作為O(1),最后對這26*10^5種情況到HASH表里面去找。這里還有一個去重復(fù)的小技巧，對于待查詢字符串m，如果出現(xiàn)的序號是k,則每次到HASH表去找時，查找到得時候用一個數(shù)組保存序號k，下次m再找到到時則忽略。?

直接上大神的代碼：

#include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; unsigned long long x[11000],key=10007,Key[110000],pre[110000],ne[110000]; char ch[110000]; int n,m,pd[11000],sign; int find(unsigned long long k){int l=1,r=n+1;while (l<r){int mid=l+r>>1;if (x[mid]==k){if (pd[mid]!=sign){pd[mid]=sign; return 1;} else return 0;}if (x[mid]>k) r=mid; else l=mid+1;}return 0; } int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%s",ch+1); int len=strlen(ch+1);for (int j=1;j<=len;j++) x[i]=x[i]*key+ch[j];}Key[0]=1;for (int i=1;i<=100000;i++) Key[i]=Key[i-1]*key;sort(x+1,x+n+1);for (;m;m--){scanf("%s",ch+1); int len=strlen(ch+1); int ans=0; sign++;for (int j=1;j<=len;j++) pre[j]=pre[j-1]*key+ch[j];ne[len+1]=0;for (int j=len;j;j--) ne[j]=ne[j+1]+ch[j]*Key[len-j];for (int i=0;i<=len;i++)for (int j='a';j<='z';j++){unsigned long long now=pre[i]*Key[len-i+1]+j*Key[len-i]+ne[i+1];ans+=find(now);}printf("%d\n",ans);}return 0; } View Code

再附上我的又亂又長的代碼：

// // main.cpp // hc17 // // Created by 陳加壽 on 15/12/27. // Copyright (c) 2015年 chenhuan001. All rights reserved. // #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <map> #include <set> #include <string> #include <algorithm> using namespace std; #define K 31 unsigned long long myhash[10010]; char str[100100]; unsigned long long g[100100]; int n,m;int tsave[10010]; int tcnt; int tmark[10010];map<unsigned long long,int> mhash; set<unsigned long long> mark;int myfind(unsigned long long x) {//找到x在myhash中出現(xiàn)的次數(shù)int b=1,d=n;while(b<d){int mid=(b+d)/2;if( x <= myhash[mid] )d = mid;else b = mid+1;}if(myhash[b]!=x || tmark[b]==1) return 0;tmark[b]=1;tsave[ tcnt++ ]=b;return 1;int tb=b;b=1,d=n;while(b<d){int mid=(b+d+1)/2;if( x >= myhash[mid] )b = mid;else d= mid-1;}return b-tb+1; }int main() {scanf("%d%d",&n,&m);//mhash.clear();for(int i=1;i<=n;i++){scanf("%s",str);unsigned long len=strlen(str);unsigned long long tmp=1;unsigned long long sum=0;for(int j=0;j<len;j++){sum += tmp*(str[j]-'a'+1);tmp = tmp*K;}//mhash[sum]++;myhash[ i ] = sum;}sort(myhash+1,myhash+n+1);memset(tmark,0,sizeof(tmark));for(int i=0;i<m;i++){//mark.clear();tcnt=0;scanf("%s",str);int len=strlen(str);unsigned long long tmp=1;for(int j=0;j<len;j++){g[j] = tmp*(str[j]-'a'+1);tmp = tmp*K;}for(int j=len-2;j>=0;j--){g[j] += g[j+1];}g[len]=0;int ans=0;tmp = 1;unsigned long long nw=0;for(int j=-1;j<len;j++){for(int p=1;p<=26;p++){unsigned long long tt=nw+p*tmp+g[j+1]*K;if(myfind(tt)==1){ans++;}}nw += tmp*(str[j+1]-'a'+1);tmp *=K;}for(int j=0;j<tcnt;j++)tmark[ tsave[j] ]=0;printf("%d\n",ans);}return 0; } View Code

?

1261解法：

這題有個十分關(guān)鍵的思路，在比賽的時候沒有想到。--! 真是蒟蒻。

假設(shè)有字符串s和字符串t，如果s要恰好添加兩個字符變成t，普通的思維至少得要26*len(s)^2次操作才能完成。但是用兩邊向中心的經(jīng)典思考方式，于是就可以在s中添加一個字符，從t中刪除一個字符。使用HASH復(fù)雜度變?yōu)閘en(s)*26。

同理剩下來兩種情況。

#include <iostream> #include <stdio.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; #define HASHN 5000007 #define INF 10000000#define K 31 typedef unsigned long long ull;vector<ull>s[10100]; vector<ull>t[10100];//不需要二分，不需要排序。struct HashNode {int next;ull key;//防止沖突int id; }hashnode[3000000];int pre[ HASHN ],cnt; int ansans[100100][3][3];void hash_insert(ull key,int id) {int hashkey = key%HASHN;int num=0;for(int p=pre[hashkey];p!=-1;p = hashnode[p].next){ull nkey = hashnode[p].key ;int nid = hashnode[p].id ;if( nkey == key ){if(id==nid) return ;num++;if(num>=3) return ;//有三個了,直接返回. }}//沒有找到相同的，或者相同數(shù)目不超過三個,則插入hashnode[cnt].key = key;hashnode[cnt].id = id;hashnode[cnt].next = pre[hashkey];pre[ hashkey ] = cnt++; }void update(int s[3],int x) {if(x==s[0]||x==s[1]||x==s[2]) return ;if(x<s[0]){s[2]=s[1];s[1]=s[0];s[0]=x;}else if(x<s[1]){s[2]=s[1];s[1]=x;}else if(x<s[2]) s[2]=x; }void myfind(ull x,int s[3]) {//找到x在myhash中出現(xiàn)的次數(shù)int hashkey = x%HASHN;for(int p=pre[hashkey];p!=-1;p=hashnode[p].next){ull nkey = hashnode[p].key ;int nid = hashnode[p].id ;if(nkey==x){update(s,nid);}}return ; }int main(int argc, const char * argv[]) {int n,m;scanf("%d%d",&n,&m);char str[100100];unsigned long len;for(int i=0;i<n;i++){scanf("%s",str);len=strlen(str);for(int j=0;j<len;j++)s[i].push_back(str[j]-'a'+1);}for(int i=0;i<m;i++){scanf("%s",str);unsigned long len=strlen(str);for(int j=0;j<len;j++)t[i].push_back(str[j]-'a'+1);}//第一個問題。t添加兩個字母,等價于s刪除一個，t添加一個//第一步，將s進行hashcnt=0;memset(pre,-1,sizeof(pre));ull savetmp[100100];for(int i=0;i<n;i++){len = s[i].size();ull tmp=1;for(int j=1;j<len;j++){savetmp[j] = tmp*s[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=1;j--)savetmp[j] += savetmp[j+1];tmp=1;ull sum=0;for(int j=0;j<len;j++)//刪除第j個點 {hash_insert(sum+savetmp[j+1],i);sum += s[i][j]*tmp;tmp *= K;}}int ans[3];/*for(int i=0;i<nodecnt;i++){printf("nodecnt%d : key=%lld id=%d\n",i,g[i].key,g[i].id);}*/for(int i=0;i<m;i++){len = t[i].size();ull tmp=K;for(int j=0;j<len;j++){savetmp[j] = tmp*t[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=0;j--)savetmp[j] += savetmp[j+1];ans[0]=ans[1]=ans[2]=INF;ull sum=0;tmp=1;for(int j=0;j<=len;j++){for(int k=1;k<=26;k++){myfind(sum+k*tmp+savetmp[j],ans);}sum += tmp*t[i][j];tmp *= K;}for(int j=0;j<3;j++){if(ans[j]!=INF) ansans[i][0][j]=ans[j]+1;else ansans[i][0][j]=-1;}//printf("\n"); }//修改兩個的時候。cnt=0;memset(pre,-1,sizeof(pre));for(int i=0;i<n;i++){len = s[i].size();ull tmp=K;for(int j=1;j<len;j++){savetmp[j] = tmp*s[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=1;j--)savetmp[j] += savetmp[j+1];tmp=1;ull sum=0;for(int j=0;j<len;j++)//修改第j個點 {for(int k=1;k<=26;k++)hash_insert(sum+tmp*k+savetmp[j+1],i);sum += s[i][j]*tmp;tmp *= K;}}/*for(int i=0;i<nodecnt;i++){printf("nodecnt%d : key=%lld id=%d\n",i,g[i].key,g[i].id);}*/for(int i=0;i<m;i++){len = t[i].size();ull tmp=1;for(int j=0;j<len;j++){savetmp[j] = tmp*t[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=0;j--)savetmp[j] += savetmp[j+1];ans[0]=ans[1]=ans[2]=INF;ull sum=0;tmp=1;for(int j=0;j<len;j++){for(int k=1;k<=26;k++){myfind(sum+k*tmp+savetmp[j+1],ans);}sum += tmp*t[i][j];tmp *= K;}for(int j=0;j<3;j++){if(ans[j]!=INF) ansans[i][1][j]=ans[j]+1;else ansans[i][1][j]=-1;}}//刪除兩個cnt=0;memset(pre,-1,sizeof(pre));for(int i=0;i<n;i++){len = s[i].size();ull tmp=K;for(int j=0;j<len;j++){savetmp[j] = tmp*s[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=0;j--)savetmp[j] += savetmp[j+1];tmp=1;ull sum=0;for(int j=0;j<=len;j++)//添加第j個點 {for(int k=1;k<=26;k++)hash_insert(sum+tmp*k+savetmp[j],i);sum += s[i][j]*tmp;tmp *= K;}}/*for(int i=0;i<nodecnt;i++){printf("nodecnt%d : key=%lld id=%d\n",i,g[i].key,g[i].id);}*/for(int i=0;i<m;i++){len = t[i].size();ull tmp=1;for(int j=1;j<len;j++){savetmp[j] = tmp*t[i][j];tmp *= K;}savetmp[len] = 0;for(int j=len-1;j>=1;j--)savetmp[j] += savetmp[j+1];ans[0]=ans[1]=ans[2]=INF;ull sum=0;tmp=1;for(int j=0;j<len;j++){myfind(sum+savetmp[j+1],ans);sum += tmp*t[i][j];tmp *= K;}for(int j=0;j<3;j++){if(ans[j]!=INF) ansans[i][2][j]=ans[j]+1;else ansans[i][2][j]=-1;}}for(int i=0;i<m;i++)for(int j=0;j<3;j++){for(int k=0;k<3;k++)printf("%d ",ansans[i][j][k]);printf("\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的hihocoder1260,1261 (HASH经典题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。