Codeforces727E-Games on a CD

Codeforces727E-Games on a CD

题意

给一个字符串\(s\)（从一个环上的某点切开得到），其长度为n*k（由n个长度为k的子串拼成），以及t个长度为k的字符串，问这t个字符串能否按一定顺序首尾相接，拼成原环（如果可以，依次打印出第i个使用的字符串的序号）

题解

因为原串是个环，所以先将字符串变成两倍。将给出的t个串Hash（双模数），将其存入map中。在原串中从1到k枚举起点i，如果能将它分成t个长度k的子串，且Hash值均在map中，并且没有在本次操作中已经使用过，那么就输出答案。

注

1、vis[i]表示序号为i的字符串在第几次被使用过
2、要用双哈希，一开始只用了一个模数被卡了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
const int base=131;
int mod[2]={1000000007,998244353};

int n,k,t,len;
char s[N],tmp[N];
ll Hash[N][2];
map<pair<ll,ll>,int> m;
int ans[N],vis[N];
ll sum[2];

//vis
//双哈希 

void init(){
    sum[0]=sum[1]=1;
    for(int i=1;i<=k;i++){
        sum[0]=(sum[0]*base)%mod[0];
        sum[1]=(sum[1]*base)%mod[1];
    } 
}

void getHash(){
    for(int i=1;i<=len;i++){
        Hash[i][0]=(Hash[i-1][0]*base%mod[0]+s[i])%mod[0]; 
        Hash[i][1]=(Hash[i-1][1]*base%mod[1]+s[i])%mod[1];
    }
}

bool solve(int st){
    int l=st,r=st+k-1;
    for(int i=1;i<=n;i++){
        ll now0=(Hash[r][0]-Hash[l-1][0]*sum[0]%mod[0]+mod[0])%mod[0];
        ll now1=(Hash[r][1]-Hash[l-1][1]*sum[1]%mod[1]+mod[1])%mod[1];
        pair<ll,ll> p=make_pair(now0,now1);
        if(!m.count(p)) return 0;
        if(vis[m[p]]==st) return 0;
        ans[i]=m[p];
        vis[ans[i]]=st;
        l+=k;r+=k;
    } 
    return 1;
}

int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    len=n*k;
    for(int i=len+1;i<=2*len;i++) s[i]=s[i-len];
    s[2*len+1]='\0';
    len*=2;
    init();
    getHash();
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%s",tmp+1);
        ll hash0=0,hash1=0; 
        for(int j=1;j<=k;j++){
            hash0=(hash0*base%mod[0]+tmp[j])%mod[0];
            hash1=(hash1*base%mod[1]+tmp[j])%mod[1];
        }
        m[make_pair(hash0,hash1)]=i;
    }
    bool flag=0;
    for(int i=1;i<=k;i++){
        if(solve(i)){
            flag=1;
            break;
        }
    }
    if(flag){
        printf("YES\n");
        for(int i=1;i<=n;i++){
            if(i!=1) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }else printf("NO\n");
    return 0;
} 

Codeforces727E-Games on a CD

原文：https://www.cnblogs.com/qjy73/p/12498585.html