题解：P17214 [ICPC 2017 Nanning R] Banned Patterns

Daybreak_Firefly · 2026-08-10 01:14:34 · 题解

对于一个字符串我们可以将每个点的权值设为与上一个相同颜色的距离，若没有则权值设为 0。

显然直接使用 AC 自动机是困难的，所以我们放弃 AC 自动机，选择 hash 维护。

显然我们可以滑动窗口维护一个字符串每个固定长度子串的 hash 值，而模式串本质不同的长度只有根号个，所以对于每种长度都求一遍就行。

复杂度带根号。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ull unsigned long long
using namespace std;
using namespace __gnu_pbds;
const int N=1e6+5,M=1e5+5,B=233;
ull pos[M];
int last[26],pre[N],suf[N];
gp_hash_table<ull,null_type> mp[M];
const int SZ=1<<20;
char buf[SZ],*p1,*p2;
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
    int x=0;char c=gc();
    while(c<'0'||c>'9')c=gc();
    while(c>='0'&&c<='9')x=x*10+(c^48),c=gc();
    return x;
}
void read_str(char *s){
    char c=gc();
    while(c<=' ')c=gc();
    while(c>' '){*s++=c;c=gc();}
    *s='\0';
}
int main(){
    pos[0]=1;
    for(int i=1;i<=1e5;i++)pos[i]=pos[i-1]*B;
    int t,_=0;t=read();
    while(t--){
        ++_;
        printf("Case #%d: ",_);
        int n,m;n=read();
        vector<int>gty;
        for(int i=1;i<=n;i++){
            memset(last,0,sizeof(last));
            char s[M];read_str(s);
            int len=strlen(s);
            ull ret=0;
            for(int j=1;j<=len;j++){
                int d=(j-last[s[j-1]-'A'])%j;
                ret=ret*B+d;
                last[s[j-1]-'A']=j;
            }
            mp[len].insert(ret);
            gty.push_back(len);
        }
        sort(gty.begin(),gty.end());
        auto zyq=unique(gty.begin(),gty.end());
        gty.erase(zyq,gty.end());
        m=read();
        while(m--){
            bool flag=0;
            char str[N];read_str(str);
            int len=strlen(str);
            memset(last,0,sizeof(last));
            pre[0]=suf[0]=0;
            for(int i=1;i<=len;i++){
                suf[i]=pre[i]=0;
                pre[i]=last[str[i-1]-'A'];
                suf[last[str[i-1]-'A']]=i;
                last[str[i-1]-'A']=i;
            }
            for(auto L:gty){
                if(L>len)break;
                ull ret=0;
                for(int i=1;i<=L;i++){
                    int d=(i-pre[i])%i;
                    ret=ret*B+d;
                }
                if(mp[L].find(ret)!=mp[L].end()){
                    flag=1;
                    printf("Y ");
                    break;
                }
                for(int i=1;i<=len-L;i++){
                    if(suf[i]&&suf[i]<=i+L-1)
                        ret-=pos[i+L-1-suf[i]]*(suf[i]-i);
                    int p=i+L;
                    int d=(pre[p]>=i+1)?(p-pre[p]):0;
                    ret=ret*B+d;
                    if(mp[L].find(ret)!=mp[L].end()){
                        flag=1;
                        printf("Y ");
                        break;
                    }
                }
                if(flag)break;
            }
            if(!flag)printf("N ");
        }
        printf("\n");
        for(auto len:gty)mp[len].clear();
    }
    return 0;
}