问题描述

  1. 如何查找PDF文件中的某段文字,可以预处理
  2. DNA序列中有很多重复,如何找到最长重复字串?

从前缀树开始

引理:一个子串一定是字符串的后缀的前缀。

我们找到所有可能的后缀,然后构造一个前缀树:

nonsense的后缀树