2020-2021:teams:legal_string:字典树_trie_lgwza
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:字典树_trie_lgwza [2020/07/16 22:08] lgwza 创建 |
2020-2021:teams:legal_string:字典树_trie_lgwza [2020/07/16 22:13] (当前版本) lgwza [检索字符串] |
||
|---|---|---|---|
| 行 51: | 行 51: | ||
| 字典树最基础的应用——查找一个字符串是否在“字典”中出现过。 | 字典树最基础的应用——查找一个字符串是否在“字典”中出现过。 | ||
| - | <HTML><blockquote> | ||
| [[https://www.luogu.com.cn/problem/P2580|于是他错误的点名开始了]] | [[https://www.luogu.com.cn/problem/P2580|于是他错误的点名开始了]] | ||
| 行 62: | 行 61: | ||
| > 对所有名字建 trie，再在 trie 中查询字符串是否存在、是否已经点过名，第一次点名时标记为点过名。 | > 对所有名字建 trie，再在 trie 中查询字符串是否存在、是否已经点过名，第一次点名时标记为点过名。 | ||
| - | <HTML><blockquote> | ||
| 参考代码 | 参考代码 | ||
| 行 108: | 行 106: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code></blockquote></HTML></blockquote></HTML> | + | </code> |
| ==== AC 自动机 ==== | ==== AC 自动机 ==== | ||
| 行 117: | 行 115: | ||
| 将数的二进制表示看做一个字符串，就可以建出字符集为 $\{0,1\}$ 的 trie 树。 | 将数的二进制表示看做一个字符串，就可以建出字符集为 $\{0,1\}$ 的 trie 树。 | ||
| - | <HTML><blockquote> | ||
| [[https://www.luogu.com.cn/problem/P4551|BZOJ1954 最长异或路径]] | [[https://www.luogu.com.cn/problem/P4551|BZOJ1954 最长异或路径]] | ||
| 行 134: | 行 131: | ||
| > 贪心的正确性：如果这么走，这一位为 $1$；如果不这么走，这一位就会为 $0$。而高位是需要优先尽量大的。 | > 贪心的正确性：如果这么走，这一位为 $1$；如果不这么走，这一位就会为 $0$。而高位是需要优先尽量大的。 | ||
| - | <HTML><blockquote> | ||
| 参考代码： | 参考代码： | ||
| 行 201: | 行 197: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code></blockquote></HTML></blockquote></HTML> | + | </code> |
| ==== 维护异或和 ==== | ==== 维护异或和 ==== | ||
2020-2021/teams/legal_string/字典树_trie_lgwza.1594908525.txt.gz · 最后更改: 2020/07/16 22:08 由 lgwza
