题解 CF727E 【Games on a CD】
sdxjzsq
2020-03-18 19:41:06
### 题目链接
https://www.luogu.com.cn/problem/CF727E
https://codeforces.com/problemset/problem/727/E
### 题意
已知$g$个长度为$k$互不相同的字符串$r[1..g]$和一个长度为$n\times k$的环形字符串$s$,问是否能从$r[1..g]$中选出$n$个组成字符串$s$。如果能,则输出`YES`,并在第二行按在$s$中的顺序输出对应的$r$的编号,否则输出`NO`。
### 思路
算法:字符串哈希(双哈希)
首先,因为本题的字符串$s$是一个环,所以读入以后需要复制一遍(其实只复制前$k$个字符就可以。)
之后,把$r[1..g]$的双哈希值放入map中,值为字符串的编号。
接着,因为环形字符串$s$划分为长度为$k$的划分方法只可能有$k$种,也就是只能把$s[1],s[2],\cdots,s[k]$作为划分后第一个字符串的第一个字符,$s[k+1]$就与第一种划分方式重复了(这就是为什么我前面说只需要复制前$k$个字符就可以)。所以枚举$s[1],s[2],\cdots,s[k]$作为划分后第一个字符串第一个字符的情况,对于每个$s$的长度为$k$的子串在map中匹配并记录编号,如果曾经匹配过或者不在map中直接进入下一次枚举即可。
复杂度$O(n\times k)$
### Tips
1. 本题一定要用双哈希,大概尝试了好多模数,最多也就撑到测试点22,换了双哈希以后直接就A掉了。
2. 双哈希判断相同字符串的条件的时候,必须是两个哈希值之前同时出现过才是相同字符串,因为这个被卡了好几次提交...
3. 双哈希用map记录编号的时候可以将map定义为`map<pair<long long,long long>,int> M`,这样就可以用`M[make_pair(foo_1,foo_2)]=bar`来记录数据了。
### code
``` cpp
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
const int maxn = 2e6+7;
long long mod = 998244353,mod2 = 1e9+7,base = 131;
map<pair<long long,long long>,int> M;//Tips3
map<long long,int>N,N2;
//其实N也可以定义成和M一样的形式,甚至可以把get_hash都写成pair的返回值,但是懒得改了咕咕咕
int n,m,k,t,ans[maxn];
char s[maxn];
long long h[maxn],h2[maxn],p[maxn],p2[maxn],g[maxn],g2[maxn];
inline long long get_hash(int l,int r)
{
return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod;
}
inline long long get_hash2(int l,int r)
{
return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}
int main()
{
scanf("%d%d%s%d",&n,&k,s+1,&t);m=n*k;p[0]=1;p2[0]=1;
for(register int i=1;i<=m;i++)s[i+m]=s[i];m<<=1;
for(register int i=1;i<=m;i++)
h[i]=(h[i-1]*base+s[i])%mod,h2[i]=(h2[i-1]*base+s[i])%mod2,//计算哈希
p[i]=p[i-1]*base%mod,p2[i]=p2[i-1]*base%mod2;
for(register int j=1;j<=t;j++)
{
scanf("%s",s+1);
for(register int i=1;i<=k;i++)g[j]=(g[j]*base+s[i])%mod,g2[j]=(g2[j]*base+s[i])%mod2,M[make_pair(g[j],g2[j])]=j;
}
for(register int j=1;j<=k;j++)
{
N.clear();N2.clear();bool flag=true;
for(register int i=0;i<n;i++)
{
long long now = get_hash(i*k+j,i*k+j+k-1),now2 = get_hash2(i*k+j,i*k+j+k-1);
if((N.count(now)&&N2.count(now2))||(M.count(make_pair(now,now2))==0)){flag=false;break;}//Tips2这里一定要now和now2同时出现过才需要退出!
N[now]=N2[now2]=1;ans[i+1]=M[make_pair(now,now2)];//记录出现情况并记录答案
}
if(flag)
{
printf("YES\n");
for(register int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
}
printf("NO");
return 0;
}
```