POJ1816 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;
}