题目概述

CF1476E

解题报告

如果用模式串来匹配给出的串，复杂度显然炸了。但是我们发现，字符串长度很短，所以如果用给出的串来匹配模式串（枚举哪些位置改成_），复杂度就只有 $O(2^4)$ 。

然后就是决定谁先谁后，这显然是个拓扑问题。每次给出的串就是建边的过程，从匹配的模式串 $x$ 连向其余能匹配的模式串，最后刷拓扑判环即可。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000,maxi=531441,maxe=maxi*16;

int n,m,len,a[maxn+5];
char s[maxn+5][10],t[10],tem[10];
int K,c[maxn+5],ID[maxn+5];vector<int> e[maxi+5];
int E,lnk[maxi+5],nxt[maxe+5],son[maxe+5],D[maxi+5];
int Head,Tail,que[maxi+5],dis[maxi+5];
bool fr=true;

int Hash(char *s){
    int ha=0;
    for (int i=0;i<len;i++) ha=ha*27+(s[i]=='_'?26:s[i]-'a');
    return ha;
}
bool check(char *a,char *b){
    for (int i=0;i<len;i++) if (b[i]!='_' && a[i]!=b[i]) return false;
    return true;
}
inline void Add(int x,int y) {son[++E]=y;D[y]++;nxt[E]=lnk[x];lnk[x]=E;}
inline bool cmp(const int &i,const int &j) {return dis[c[i]]<dis[c[j]];}
void Print(int x) {if (fr) fr=false; else putchar(' ');printf("%d",x);}
int main(){
    scanf("%d%d%d",&n,&m,&len);
    for (int i=1;i<=n;i++){
        scanf("%s",s[i]);a[i]=Hash(s[i]);
        if (e[a[i]].empty()) c[++K]=a[i];e[a[i]].push_back(i);
    }
    for (int i=1;i<=m;i++){
        int x;scanf("%s%d",t,&x);
        if (!check(t,s[x])) {puts("NO");return 0;}
        for (int s=0;s<(1<<len);s++){
            for (int i=0;i<len;i++) s>>i&1?tem[i]='_':tem[i]=t[i];
            int ha=Hash(tem);if (a[x]!=ha && e[ha].size()) Add(a[x],ha);
        }
    }
    for (int i=1;i<=K;i++) if (!D[c[i]]) que[++Tail]=c[i];
    while (Head!=Tail){
        int x=que[++Head];
        for (int j=lnk[x],u;j;j=nxt[j])
            if (!(--D[u=son[j]])) que[++Tail]=u,dis[u]=dis[x]+1;
    }
    if (Tail!=K) {puts("NO");return 0;}
    for (int i=1;i<=K;i++) ID[i]=i;sort(ID+1,ID+1+K,cmp);
    puts("YES");
    for (int k=1,i=ID[k];k<=K;k++,i=ID[k])
        for (int j=0,si=e[c[i]].size();j<si;j++)
            Print(e[c[i]][j]);
    puts("");return 0;
}