Wild Words题解
1.题目大意
先给你 \(n\) 个字符串，这些字符串包含小写字母，？和 *。
其中， ? 可以表示任意一个字符，* 可以表示任意长度的任意字符（包括0个）
然后 \(m\) 次询问，每次给你一个字符串，问你它和哪些字符串匹配
2.做法
可以在字典树上 \(dfs\)
先定义一下字典树节点要存储的信息：该节点代表的字符串在一开始 \(n\) 个字符串中的位置，开个vector<int>
首先，将字符串插入字典树，这里很简单，还是该怎么插怎么插
只是?和*比较特殊，我们需要将它们赋予两个特殊的编号，就26和27吧（紧接着25）
而且到了最后一个节点时，我们需要将当前插入字符串的编号加入最后一个节点的vector里。
接下来，是最令人头疼的查询
我们发现，?和*会影响字符串的匹配判断
因为它们会导致匹配“跳步”
比如这两个字符串，第二个去判断匹不匹配第一个字符串
zou*wa?66
zoupiwa666
我们发现，当匹配到*时，可以无视它是否与p匹配，我们可以直接跳到w（也可以是那之后的任何一个字符）进行接下来的匹配判断，?也差不多，只不过只能往后跳一位罢了。
所以这时候我们就不能按部就班的去遍历字典树了
我们需要使用 \(dfs\) 来遍历
设 dfs(int u,int dep,string s)
\(u\) ：当前遍历到的字典树上的节点
\(dep\) ：当前匹配到了第几个字符
\(s\) ：要匹配的字符串
分四种情况：
- 边界：当
dep==s.size()时，把当前 \(u\) 节点上存储的所有下标加入到存储答案的vector中 - \(u\)的下一个字符可以是
*：当son[u][27]>0时，去进行跳步，也就是可以直接跳到dfs(son[u][27],i,s)注意这里 \(dep \le i \le s.size()\)，因为有*时可以随意匹配 - \(u\)的下一个字符可以是
?：当son[u][26]>0时，往后跳一位，也就是跳到dfs(son[u][27],dep+1,s) - \(u\)的下一个字符成功与询问串匹配 ：这是最基本的，直接跳到
dfs(son[u][ch],dep+1,s)
注意：
刚刚的第二步要放到第一步边界之前，因为有可能查询串最后一个字符是
*要对答案排序、去重
3.Code
#include<bits/stdc++.h>
using namespace std;
int son[1000010][28],n,m,cnt=1;
vector<int>pos[1000010],ans;
inline int getnum(char ch){if(ch>='a' and ch<='z')return ch-'a';if(ch=='?')return 26;return 27;
}
inline void insert(string s,int id){int now=1;for(auto c:s){int ch=getnum(c);if(!son[now][ch])son[now][ch]=++cnt;now=son[now][ch];}pos[now].push_back(id);
}
inline void dfs(int u,int dep,string s){if(son[u][27])for(int i=dep;i<=s.size();i++)dfs(son[u][27],i,s);if(dep==s.size()){for(auto v:pos[u])ans.push_back(v);return;}int ch=getnum(s[dep]);if(son[u][ch])dfs(son[u][ch],dep+1,s);if(son[u][26])dfs(son[u][26],dep+1,s);
}
main(){cin.tie(0)->ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){string t;cin>>t;insert(t,i-1);}//cout<<cnt;for(int i=1;i<=m;i++){ans.clear();string s;cin>>s;dfs(1,0,s);sort(ans.begin(),ans.end());ans.resize(unique(ans.begin(),ans.end())-ans.begin());if(ans.size()==0)cout<<"Not match";for(auto x:ans)cout<<x<<' ';cout<<'\n';}return 0;
}