題目鏈接：點擊查看

題目大意：給出 $n$ 個模式串和 $m$ 個匹配串，題目要求輸出一種模式串的排列方式，使得 $m$ 個模式串從頭開始匹配的話，可以匹配到相應的模式串

模式串的長度不超過 $4$，兩兩互不相同，含有通配符 “_”

題目分析：一開始想的是對模式串狀壓，模式串的每個位置都有 $26$ 種情況，一個模式串可以匹配 $4^{26}$ 個匹配串，可以預處理哈希，但是后續的處理不太會快速建圖，遂放棄

看了題解后發現可以反過來想，每個匹配串若想匹配模式串，那么每個位置要么匹配原字符，要么匹配通配符，也就是每個匹配串可以匹配至多 $2^4=16$ 個模式串，確實這樣一來就比較好處理了

至于建圖，可以建一個有 $n$ 個點，$16?m$ 條邊的有向圖，然后跑拓撲就可以了

因為題目保證了任意兩個模式串互不相同，所以可以用字典樹完成字符串的匹配，以及在字典樹上dfs搜索

代碼：

// Problem: E. Pattern Matching // Contest: Codeforces - Educational Codeforces Round 103 (Rated for Div. 2) // URL: https://codeforces.com/contest/1476/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; bool flag; int in[N],n,m,k; char s[N]; vector<int>node[N]; int trie[N][27],id[N],tot; int newnode() {tot++;memset(trie[tot],0,sizeof(trie[tot]));return tot; } void addedge(int x,int y) {node[x].push_back(y);in[y]++; } void insert(int i) {int pos=0;for(int i=1;i<=k;i++) {int to=s[i]=='_'?26:s[i]-'a';if(!trie[pos][to]) {trie[pos][to]=newnode();}pos=trie[pos][to];}id[pos]=i; } void search(int pos,int step,int x) {if(step>k) {if(id[pos]==x) {flag=true;} else {addedge(x,id[pos]);}return;}if(trie[pos][s[step]-'a']) {search(trie[pos][s[step]-'a'],step+1,x);}if(trie[pos][26]) {search(trie[pos][26],step+1,x);} } void topo() {vector<int>ans;queue<int>q;for(int i=1;i<=n;i++) {if(!in[i]) {q.push(i);}}while(q.size()) {int u=q.front();q.pop();ans.push_back(u);for(auto v:node[u]) {if(--in[v]==0) {q.push(v);}}}if(ans.size()==n) {puts("YES");for(auto it:ans) {printf("%d ",it);}} else {puts("NO");} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(m),read(k);for(int i=1;i<=n;i++) {scanf("%s",s+1);insert(i);}while(m--) {scanf("%s",s+1);int id;read(id);flag=false;search(0,1,id);if(!flag) {return 0*puts("NO");}}topo();return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1476E Pattern Matching(字典树+拓扑)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。