给你一个长度为n*k的环，环上每一个位置有一个字符。 现在给你g个长度为k的字符串，问是否可以在g个字符串中找出k个构成这个环。
有0到k枚举，然后双hash就可以。
#include <iostream> #include <map> #include <cstring> #include <vector> using namespace std; const int MAXN=3e6+10; char str1[MAXN],str2[MAXN]; const int seed=13331; const int mod1=1000000007; const int mod2 = 19260817; typedef long long ll; typedef pair<ll,ll> pll; ll xp[2][MAXN],hash_1[2][MAXN],hash_2[2][MAXN]; pll temp[MAXN]; int ans[MAXN]; void init() { xp[0][0]=1; for(int i=1;i<MAXN;i++) xp[0][i]=(xp[0][i-1]*13331)%mod1; xp[1][0]=1; for(int i=1;i<MAXN;i++) xp[1][i]=(xp[1][i-1]*1331)%mod2; } pll get_hash(int i,int l,ll hash[][MAXN]) { ll a=((hash[0][i]-hash[0][i+l]*xp[0][l])%mod1+mod1)%mod1; ll b=((hash[1][i]-hash[1][i+l]*xp[1][l])%mod2+mod2)%mod2; return pll(a,b); } pll make_hash(char str[],ll hash[][MAXN]) { int len=strlen(str); hash[0][len]=0; hash[1][len]=0; for(int i=len-1;i>=0;i--) { hash[0][i]=(hash[0][i+1]*13331%mod1+str[i]-'a'+1)%mod1; hash[1][i]=(hash[1][i+1]*1331%mod2+str[i]-'a'+1)%mod2; } return get_hash(0,len,hash); } map<pll,int> mp; map<pll,vector<int>> mp2; int main() { int n,k; init(); scanf("%d%d",&n,&k); scanf("%s",str1); int len=n*k; for(int i=len;i<len+len;i++) str1[i]=str1[i-len]; make_hash(str1,hash_1); int g; scanf("%d",&g); for(int i=0;i<g;i++) { scanf("%s",str2); pll t1=make_hash(str2,hash_2); mp2[t1].push_back(i+1); mp[t1]++; } for(int i=0;i<k;i++) { int fg=1; int cont=0; int cont1=0; for(int j=i;j<=i+len-k;j+=k) { pll t2=get_hash(j,k,hash_1); if(!mp[t2]) { fg=0; break; } else { temp[cont++]=t2; mp[t2]--; ans[cont1++]=mp2[t2].back(); mp2[t2].pop_back(); } } if(fg) { printf("YES\n"); for(int j=0;j<cont1;j++) if(!j) printf("%d",ans[j]); else printf(" %d",ans[j]); return 0; } else { for(int j=0;j<cont;j++) { mp[temp[j]]++; mp2[temp[j]].push_back(ans[j]); } } } printf("NO\n"); return 0; }
