We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.
展开▼
机译：我们展示了如何在对文本中的字符进行排序之后，以线性时间构造文本字符串 t 的后缀树，以便搜索模式 p 花费时间 O （ p + log t ），与字母大小无关，从而匹配后缀数组的渐近性能。然后，使用这些后缀树或后缀数组，我们可以提供线性时间算法，用于在任何固定维度上进行模式匹配。
展开▼
