题目链接：传送门
思路：由于MOD只有9983大小，所以四位小写字母的字符串组合有26+26^2+26^3+26^4=475254种组合。
所以只要每次枚举出从1到475254中的hash值对应的字符串记录在数组中，然后以O(1)的方式查找即可。
注意：
（1）每个字符串对应一个唯一的值，所以按照字符串的顺序递增来组成hash值。
（2）注意index会与其他函数名称冲突，造成编译错误，要改一下。
#include<bits/stdc++.h> using namespace std; const int MOD = 9983; const int maxn = 1e5+10; int p,q,r,t,mul[50],Index[50],vis[MOD]; string res[maxn][2],ss,str; void Init() { ss="a"; mul[0]=p;mul[1]=q;mul[2]=r; for(int i=0;i<26;i++) Index[i]=i*t+t; for(int i=0;i<maxn;i++) res[i][0]=res[i][1]=""; memset(vis,0,sizeof(vis)); } void add() { int len=ss.size(); ss[len-1]++; while(ss[len-1]>‘z‘&&len>=2){ ss[len-1]=‘a‘; ss[len-2]++; len--; } if(ss[0]>‘z‘){ ss[0]=‘a‘; ss=‘a‘+ss; } } int getsum(string st) { int ans=0; for(int i=0;i<st.length();i++){ ans=(ans*mul[(i+1)%3]+Index[st[i]-‘a‘])%MOD; } return ans; } int main(void) { int i,j,tmp,k,ff,T; while(~scanf("%d%d%d%d",&p,&q,&r,&t)){ Init(); for(int i=1;i<maxn;i++){ tmp=getsum(ss); if(vis[tmp]) res[tmp][1]=ss; else res[tmp][0]=ss; vis[tmp]=1; add(); } scanf("%d",&T); while(T--){ cin>>str; tmp=getsum(str); if(str==res[tmp][1]) cout<<res[tmp][0]<<endl; else cout<<res[tmp][1]<<endl; } } return 0; }
原文：https://www.cnblogs.com/2018zxy/p/10331336.html
