# HDU-2846 字典树拓展
## [HDU-2846](http://acm.hdu.edu.cn/showproblem.php?pid=2846)
## 分析
就是一个很明显的字典树.
但是! 有以下两点需要注意:
1. 要求的结果是**查询到的节点下包含的总项数**, 有线段树内味儿了. 需要**在建树时维护子项总数**, 注意这和子节点数完全不是一码事, 字典树里一个节点不一定代表一个单词.
2. 字符串的**匹配是任意位置开始的**, 比如字典是{abc, adbc}, 那么匹配bc就可以把两个都匹配到:
- 需要**给字符串的每个前向子串都构造一遍字典树**. 这时会出现重复记录的问题(比如aaa会走三次a).
- **用一个tag来标记现在构造的字符串来自哪个单词, 保证每个相关节点计数且仅计数一次. **以此来避免计数错误.
- 将子项总数维护在上级节点(生子前自己++), 会导致每个字符串的最后一个节点不进行计数, 因此还需要**结合tag, 在构造完毕后, 对 是否标记过tag 和 是否到达叶子节点 进行特判**, 给最后一个节点补计数.
因此, 如果有一个字典是**{abc, adbc, ccc, adab, bc, adbcc}**, 那么会生成如下的字典树(R代表虚根节点):
详情见代码.
## 代码
```cpp
// -------------- GLOBAL ----------------
struct node {
char c;
int cnt;
int tag; // 标记是否是同一字符串不同子串的重复构造, 避免cnt计数错误
vector<node> children;
node(char c1 = 0) : c(c1), cnt(0), tag(0) {}
friend bool operator==(const node & n1, const node & n2) { return n1.c == n2.c; }
} tree;
// -------------- FUNC ----------------
// 建立字典树
void makeTree(string s, int tag) {
node * root = &tree;
while (s.length()) {
auto found = find(stl(root->children), s[0]);
if (root->tag != tag) // 不是重复节点
++root->cnt;
root->tag = tag;
if (found != root->children.end()) { // 有节点
root = &*found;
} else { // 没节点
root->children.push_back(node(s[0]));
root = &root->children.back();
}
s = s.substr(1);
}
if (root->tag == 0 || root->tag != tag)
++root->cnt; // 它本身
}
// 查询字典树
int queryTree(string s) {
node * root = &tree;
while (s.length()) {
auto found = find(stl(root->children), s[0]);
if (found != root->children.end()) { // 有节点
root = &*found;
} else { // 没节点
return 0;
}
s = s.substr(1);
}
return root->cnt;
}
// 画图调试用的
void prtTree(node * root, string prefix) {
FE(n, root->children) {
LOG("\"%s[%d]\" -- \"%s%c[%d]\";\n", prefix.c_str(), root->cnt, prefix.c_str(), n.c, n.cnt);
prtTree(&n, prefix + n.c);
}
}
// -------------- MAIN ----------------
int main() {
ios_base::sync_with_stdio(false);
int n;
INI(n);
F1(i, n) {
string s;
INS(s);
// 这个变态题要求字符串从任意位置开始都能匹配
// 那就给他从任意位置构造!!!
// 注意这样构造必出重复, 要用tag避免重复累加
F0(j, s.length()) {
makeTree(s.substr(j), i);
}
}
prtTree(&tree, "R");
int q;
INI(q);
F0(i, q) {
string s;
INS(s);
printf("%d\n", queryTree(s));
}
return 0;
}
```
![]()