j_r*_*ker
10
[编辑17/11/2013:计算叶节点.谢谢Vinicius Pinto!]
您可以在线性时间内在文本上构建后缀树.然后,在后缀树中搜索您的子字符串; 找到它时,计算匹配节点下面的叶节点数.这是长度为m的子串的O(m + k),出现k次(添加n个术语用于构建后缀树).或者,您可以使用深度优先遍历来预先计算树中每个节点的后代数 - 这将提供O(m)查询.
对于大型文本,后缀数组在实践中通常比后缀树快,尽管搜索从O(m)到O(m log m)的单个长度为m的字符串.在这种情况下,特定子字符串的所有出现都将在后缀数组中显示为连续的块,因此该块的宽度是出现的次数.