【Technocup 2017 - Elimination Round 1 E. Games on a CD 】枚举+Hash

题目链接

http://codeforces.com/contest/727/problem/E

题意

给你一个长度为$n\times k$的环，环上每一个位置有一个字符。
现在给你$g$个长度为$k$的字符串，问是否可以在$g$个字符串中找出$k$个构成这个环。

做法

由于单个字符串长度已经确定，只需要枚举第一个串在环中的下标即可。
而且只需要枚举到$k$，因为枚举$1$和$k+1$是一样的。
对于每个枚举的起始位置，只需要每$k$个字符判断一下是不是可以在$g$个字符串中得到，这个过程用Hash直接可以做。
枚举起点$k$次，每次计算$n$个位置，总复杂度是$O(n?k)$
这题会卡掉自然溢出，所以要用多Hash，自己第一次手写这个东西，常数可能有点大。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
const int maxn = 5e6+5;
const int Mod=1000000007;
#define Se second
#define Fi first
#define pb push_back
char str[maxn];
char tmp[maxn];
ll hash_[2][maxn],xp[2][maxn];
const int Mod1 = 1000000007;
const int Mod2 = 19260817;
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;return ;
}
pll make_hash(char str[])
{
    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 pll((hash_[0][0]-hash_[0][len]*xp[0][len]%Mod1+Mod1)%Mod1,(hash_[1][0]-hash_[1][len]*xp[1][len]%Mod2+Mod2)%Mod2);
}
pll Get_hash(int i,int L)//得到起点为i，长度为L的子串的hash值
{
    return pll((hash_[0][i]-hash_[0][i+L]*xp[0][L]%Mod1+Mod1)%Mod1,(hash_[1][i]-hash_[1][i+L]*xp[1][L]%Mod2+Mod2)%Mod2);
}
pll H[maxn];
map<pll,int> mp;
map<pll,stack<int> > mp2;
vector<pll> ct;
int main()
{
    init();int n,k,m;scanf("%d%d",&n,&k);scanf("%s",str);for(int i=0;i<n*k;i++) str[i+n*k]=str[i];str[2*n*k]='\0';scanf("%d",&m);for(int i=1;i<=m;i++){
    scanf("%s",tmp);H[i]=make_hash(tmp);mp[H[i]]++;mp2[H[i]].push(i);}make_hash(str);int len=strlen(str);for(int i=0;i<k;i++){
    ct.clear();int tt=0;for(int j=i;j<i+len/2;j+=k){
    pll tmp=Get_hash(j,k);if(!mp.count(tmp)||mp[tmp]==0)  tt=1;else{
    ct.pb(tmp);mp[tmp]--;}}if(tt==0){
    puts("YES");for(int j=i;j<i+len/2;j+=k){
    pll tmp=Get_hash(j,k);int st=mp2[tmp].top();mp2[tmp].pop();printf("%d ",st);}return 0;}for(int j=0;j<ct.size();j++) mp[ct[j]]++;}puts("NO");return 0;
}