<题目链接>
题目大意:
现在给定出n个字符串,并且进行m此询问,每次询问给出一个匹配串,每次询问都给出该匹配串能够匹配的字符串个数(题目只出现字符'a'~'e')。'?'可以看成任意字符,也可以看做没有。
解题分析:
对这n个字符串建立Trie树,然后对每次输入的匹配串在trie树上进行模糊匹配,'?'的分类匹配主要体现在Trie树上的DFS过程。
#include<bits/stdc++.h>
using namespace std; const int M = ;
const int N = 1e5+;
int nxt[N*M][], val[N*M], flag[N*M];
char s[M], str[M];
int n, m, size = ; void insert(char *s){
int now = ;
for (int i=; s[i]; i++){
int to=s[i]-'a';
if (!nxt[now][to]) nxt[now][to] = ++size;
now = nxt[now][to];
}
val[now]++;
} int dfs(int loc, int now){ //u为trie树上的节点编号
if (!now) return ;
if (!str[loc]){
if (flag[now] == m+) return ; //Trie树上的同一字符串是否只匹配一次(因为下面进行了多次模糊匹配选择,可能会发生重复
else{
flag[now] = m+;
return val[now];
}
}
if (str[loc] != '?') return dfs(loc+, nxt[now][str[loc]-'a']); //如果当前字符匹配成功
//对于匹配串中为'?'字符的,具有以下两种选择
int res = dfs(loc+, now); //跳过匹配串中'?'的位置
for (int i=; i<; i++) //将'?'作为任意字符串,与Trie树上的字符进行匹配
res += dfs(loc+, nxt[now][i]);
return res;
} int main(){
scanf("%d%d", &n, &m);getchar();
for (int i=; i<=n; i++){
gets(s);
insert(s);
}
while (m--){
gets(str);
printf("%d\n", dfs(, ));
}
}
2019-02-22