这两题比赛做的时候各种卡，太久没有写过这种类型的题目了。各种细节想不清楚。 赛后看下网上大部分题解的代码，发现大部分都是直接用TRIE+暴力直接搞的--!，随便找了份代码发现有些数据这种做法是超时的，比如n=m=1,然后下面两行长度为100000的全为a的字符串。明显直接暴力DFS复杂度为n*n.
比赛的时候，还想用26*100000*log(n)然后用STL来去重复，结果直接超时果真STL还是太耗时了。。。
1260解法：
因为字符串集合S中N个字符串是两两不同的（这点比较关键，利用这点可以减少代码量），所以对S中得N个字符进行HASH处理（可以只得到HASH值不建HASH表，查询时候用二分）。然后对于需要查询的M个字符串，因为这M个字符串总长是10^5，所以在每个字符串每一位暴力插入（‘a’-‘z’）,也就是要枚举26*10^5种情况，用一次预处理可以使得每次HASH操作为O(1),最后对这26*10^5种情况到HASH表里面去找。这里还有一个去重复的小技巧，对于待查询字符串m，如果出现的序号是k,则每次到HASH表去找时，查找到得时候用一个数组保存序号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 ",ans); } return 0; }
再附上我的又乱又长的代码：
// // 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中出现的次数 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 ",ans); } return 0; }
1261解法：
这题有个十分关键的思路，在比赛的时候没有想到。--! 真是蒟蒻。
假设有字符串s和字符串t，如果s要恰好添加两个字符变成t，普通的思维至少得要26*len(s)^2次操作才能完成。但是用两边向中心的经典思考方式，于是就可以在s中添加一个字符，从t中删除一个字符。使用HASH复杂度变为len(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 ;//有三个了,直接返回. } } //没有找到相同的，或者相同数目不超过三个,则插入 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中出现的次数 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进行hash cnt=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 ",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(" "); } //修改两个的时候。 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 ",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 ",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(" "); } return 0; }