【算法2-4】字符串

题单介绍

对应进阶篇第 7 章。 字符串,就是由字符连接而成的序列。我们可以使用不同的算法来解决不同的和字符串有关 的问题。《基础篇》中介绍过的哈希表,可以将一个字符串映射为一个整数,可以高效地查询这 个字符串是否存在于一个集合中。本章介绍另外两种比较基础的字符串工具——Knuth-Morris-Pratt 算法和字典树。 Knuth-Morris-Pratt 算法,简称 KMP 算法,可以高效的从一个字符串中查询另外一个指定的 字符串是否存在;如果存在的话位置在哪里。它会利用字符串匹配过程中失败的信息,从而减少 字符串查找比较的次数。 而字典树,又称为 Trie 树,可以方便的储存、索引和查找字符串。当然除了字符串,还可以 将数字拆成二进制,存入字典树中,常常可以高效处理涉及到异或的问题。 ![](https://ipic.luogu.com.cn/djxaej.png)

题目列表

  • 【模板】KMP
  • [BOI2009] Radio Transmission 无线传输
  • 魔族密码
  • 于是他错误的点名开始了
  • 最长异或路径
  • [十二省联考 2019] 异或粽子
  • [USACO2.3] 最长前缀 Longest Prefix
  • Test
  • [POI2006] OKR-Periods of Words
  • [NOI2014] 动物园
  • [USACO08DEC] Secret Message G
  • [TJOI2010] 阅读理解
  • 最大异或和
  • [TJOI2018] 异或
  • 【模板】普通平衡树
  • 「EZEC-4」可乐