问题简介

给定词典，求给定文章内部是否含有词典中的单词。 具体问题请参考 hihocoder的网站。

算法简介

详细的算法思路参照 hihocoder的网站。 Trie树大致上是共前缀的树（具体参照 [hihocoder1014]Trie树），Trie图则是维护后缀前缀重叠最长的信息（这里结合了 KMP的思想，KMP可以看做是词典只有一个词的Trie树；KMP也是维护字符串前缀后缀最长重叠部分，之后加入短路）。Trie图的目的是减少比较次数，充分利用已知信息。

数据结构

1. 节点Node

1.1. 内部变量

对应于Trie图中的某个节点，这个结构存储几乎所有的Trie图中的信息，包括： 节点对应字符串的前缀（包括原串）是否有词典中的单词bool flag。指向子节点以及如果没有子节点时所应该跳转到的节点Node* next[26]。例如当前节点对应于字符串str，新字符'b'在Trie树中不存在子节点，则next['b']对应于所有节点中对对应字符串是str+'b'的后缀且长度最长（在Trie树中深度最深）的节点。区分指向边是否存在于Trie树中的标志，即是指向子节点还是跳转节点。bool flags[26]所有节点中对应字符串是该节点对应字符串str的后缀且长度最长（深度最深）的节点Node *trie。测试用的变量：父节点Node* parent，节点编码int num。

1.2. 内部函数

构造函数：就是给变量赋初值。析构函数：空函数复制构造函数：复制变量。递归delete的函数clean：用于清空new的Node。插入字符串函数insert(char *str):str指向于当前节点与父节点之间边的字符，str+1用于表面递归插入的方向。insert函数需要维护flag, next, next->parent几个变量。设置flag的函数set_flag(): 在所有插入函数结束之后调用，用于维护flag，即该节点对应字符串的前缀中是否含有词典中的单词。注：此处是递归版本，为了加速，已弃用。测试用print()函数：输出节点内部信息。 struct Node{ bool flags[26],flag; Node *next[26],*parent,*trie; // int parent_index; int num;//for test public: Node():flag(false),parent(NULL),trie(NULL),num(-1){ for (int i = 0;i < 26;++i){ flags[i] = false; next[i] = NULL; } } Node(const Node &n):flag(n.flag),parent(n.parent),trie(n.trie),num(n.num){ for (int i = 0;i < 26;++i){ flags[i] = n.flags[i]; next[i] = n.next[i]; } } ~Node() {} void clean(); void insert(char *str); void set_flag(bool f); //for test void print(); };

2. Trie图 TrieGraph

2.1. 内部变量

存储根节点即可

2.2. 内部函数

构造函数：空函数析构函数：调用Node.clean()函数插入函数insert()：递归调用法，调用Node.insert()设置整个图节点flag的设置set_flag()：深度优先的迭代算法由Trie树构造Trie图的函数build_graph()：具体参照详细算法部分。利用Trie图检测输入字符串中是否有词典中的词语test(char *str)：根据字符串，逐步前进，判断是否行进到flag=true的节点。测试用print()函数：输出树中某些节点内部的信息。 class TrieGraph{ Node root; public: TrieGraph() {} ~TrieGraph() {root.clean();} void insert(char *str); void set_flag(); void build_graph(); bool test(char *str); void print(); };

算法详解

为了方便复杂度的表示，设字典中单词的个数为N，长度最长为L，文章长度为M。

1. 构建Trie树的insert(char *str)函数

使用递归算法，*str决定了插入的子节点。具体参照 [hihocoder1014]Trie树。复杂度为O(L) void insert(char *str){ if (!*str) flag = true; else { if (!next[*str-'a']){ next[*str-'a'] = new Node; flags[*str-'a'] = true; next[*str-'a']->parent = this; } next[*str-'a']->insert(str+1); } }

2. 设置flag的set_flag()函数

使用迭代算法实现深度优先遍历所有节点，子节点Node的flag=Node.flag || Node.parent->flag。复杂度O(NL) void set_flag(){ stack<Node*> node_stack; Node *node = &root; node_stack.push(node); char str[100002] = {0}; int depth = 0,str_char; bool flag = false; while (!node_stack.empty()){ flag = node_stack.top()->flag; node = node_stack.top(); for (str_char=(str[depth]?str[depth]+1:'a');str_char<='z' && !node->flags[str_char-'a'];++str_char); if (str_char == 'z'+1){ node_stack.pop(); str[depth--] = 0; } else { node_stack.push(node->next[str_char-'a']); flag = flag || node->next[str_char-'a']->flag; node->next[str_char-'a']->flag = flag; str[depth++] = str_char; } } }

3. 构建Trie图build_graph()

回顾next以及trie的定义：某个节点Node根据其与根节点的路径唯一确定一个字符串str，那么trie指向的是所有节点中是str后缀且长度最长的节点；而next[char]如果是Trie树中的边则指向其子节点，否则指向所有节点中是str+char后缀且长度最长的节点（这里的两个定义在拓展后缀定义（即包含原串）的意义下是等价的，分开定义是方便函数处理）。 根据定义，可以很容易给出一种朴素的解法，即由长到短枚举所有后缀，判断是否有对应节点。复杂度为O(N*L*L*L) 分析可知这种朴素的算法有很多重复计算，字符串的trie以及next可以利用其前缀的trie以及next信息。具体来说，设len=strlen(str)，那么str的最长存在后缀为str[0:len-1]+str[len-1]的最长存在后缀，即trie(str)=next(str[0:len-1])[str[len-1]]；而str+char的最长重复后缀对应于trie(str)+char的最长重复后缀（这里是广义定义的后缀，即包含原串），即next(str)[char]=next(trie(str))[char]。综上所述，使用广度优先遍历所有节点，既可以快速的构建Trie图。复杂度为O(N*L) void build_graph(){ queue<Node*> node_queue; Node *node; //for test int cnt = 0; root.num = cnt++; root.trie = &root; for (int i = 0;i < 26;++i){ if (root.flags[i]){ node_queue.push(root.next[i]); //for test root.next[i]->num = cnt++; root.next[i]->trie=&root; } else root.next[i] = &root; } while (!node_queue.empty()){ node = node_queue.front(); node_queue.pop(); for (int i = 0;i < 26;++i){ if (node->flags[i]){ node_queue.push(node->next[i]); //for test node->next[i]->num = cnt++; node->next[i]->trie = node->trie->next[i]; } else node->next[i]=node->trie->next[i]; } } }

4. 判断给定文章是否含有词典中词语bool test(char *str)

依次按照字符串中的字符在Trie图中移动，如果移动到flag=true的节点，则返回true；否则返回false。复杂度为O(M) bool test(char *str){ Node *node = &root; while (*str){ //for test // cout << node->num << endl; node = node->next[*str-'a']; if (node->flag) return true; ++str; } return false; }

5. 主函数

构建Trie树(O(NL))-->设置flag(O(NL))-->构建Trie图(O(NL))-->判断文章是否含有词典中的词语O(M)。整体复杂度为O(NL+M)。 int main() { char str[1000002]; int N; TrieGraph trieGraph; cin >> N; for (int i = 0;i < N;++i){ cin >> str; trieGraph.insert(str); } trieGraph.set_flag(); trieGraph.build_graph(); cin >> str; cout << ((trieGraph.test(str))?"YES":"NO") << endl; // trieGraph.print(); return 0; }

全部代码

#include <iostream> #include <cstring> #include <queue> #include <stack> using namespace std; struct Node{ bool flags[26],flag; Node *next[26],*parent,*trie; // int parent_index; int num;//for test public: Node():flag(false),parent(NULL),trie(NULL),num(-1){ for (int i = 0;i < 26;++i){ flags[i] = false; next[i] = NULL; } } Node(const Node &n):flag(n.flag),parent(n.parent),trie(n.trie),num(n.num){ for (int i = 0;i < 26;++i){ flags[i] = n.flags[i]; next[i] = n.next[i]; } } ~Node() {} void clean(){ for (int i = 0;i < 26;++i) if (flags[i]){ next[i]->clean(); delete next[i]; } } void insert(char *str){ if (!*str) flag = true; else { if (!next[*str-'a']){ next[*str-'a'] = new Node; flags[*str-'a'] = true; next[*str-'a']->parent = this; // next[*str-'a']->parent->parent_index = *str-'a'; } next[*str-'a']->insert(str+1); } } void set_flag(bool f){ flag = f || flag; for (int i = 0;i < 26;++i) if (flags[i]) next[i]->set_flag(flag); } //for test void print(){ cout << num << ": "; for (int i = 0;i < 26;++i) cout << next[i]->num << '/' << flags[i] << ' '; cout << endl; } }; class TrieGraph{ Node root; public: TrieGraph() {} ~TrieGraph() {root.clean();} void insert(char *str){ if (!*str) root.flag = true; else { if (!root.next[*str-'a']){ root.next[*str-'a'] = new Node; root.flags[*str-'a'] = true; root.next[*str-'a']->parent = &root; // root.next[*str-'a']->parent_index = *str-'a'; } root.next[*str-'a']->insert(str+1); } } void set_flag(){ // root.set_flag(false); stack<Node*> node_stack; Node *node = &root; node_stack.push(node); char str[100002] = {0}; int depth = 0,str_char; bool flag = false; while (!node_stack.empty()){ flag = node_stack.top()->flag; // cout << str << endl; node = node_stack.top(); for (str_char=(str[depth]?str[depth]+1:'a');str_char<='z' && !node->flags[str_char-'a'];++str_char); if (str_char == 'z'+1){ node_stack.pop(); str[depth--] = 0; } else { node_stack.push(node->next[str_char-'a']); flag = flag || node->next[str_char-'a']->flag; node->next[str_char-'a']->flag = flag; str[depth++] = str_char; } } } void build_graph(){ queue<Node*> node_queue; Node *node; //for test int cnt = 0; root.num = cnt++; root.trie = &root; for (int i = 0;i < 26;++i){ if (root.flags[i]){ node_queue.push(root.next[i]); //for test root.next[i]->num = cnt++; root.next[i]->trie=&root; } else root.next[i] = &root; } while (!node_queue.empty()){ node = node_queue.front(); node_queue.pop(); for (int i = 0;i < 26;++i){ if (node->flags[i]){ node_queue.push(node->next[i]); //for test node->next[i]->num = cnt++; node->next[i]->trie = node->trie->next[i]; } else node->next[i]=node->trie->next[i]; } } } bool test(char *str){ Node *node = &root; while (*str){ //for test // cout << node->num << endl; node = node->next[*str-'a']; if (node->flag) return true; ++str; } return false; } void print(){ root.print(); root.next[0]->print(); root.next[1]->print(); root.next[2]->print(); root.next[0]->next[0]->print(); } }; int main() { char str[1000002]; int N; TrieGraph trieGraph; cin >> N; for (int i = 0;i < N;++i){ cin >> str; trieGraph.insert(str); } trieGraph.set_flag(); trieGraph.build_graph(); cin >> str; cout << ((trieGraph.test(str))?"YES":"NO") << endl; // trieGraph.print(); return 0; }