Question

运用后缀处理字串匹配问题

两步骤：枚举 T 的所有后缀、搜寻开头恰为 P 的后缀。

字串匹配时，P 的每个对齐位置，正是 T 的每个后缀的开头。儘管后缀意指字串后端，但是此处我们关注后缀前端。

T: mississippi
P: issi

all suffixes of T:
   mississippi, ississippi, ssissippi, ...
   
string matching:
   0             1            2
   mississippi   ississippi   ssissippi   ...
   issi          issi         issi

储存大量后缀的资料结构

以大量字串的资料结构，储存并排序 T 的全部后缀，就更容易搜寻后缀。例如 Array、Binary Tree、Trie、Automaton。

后缀之间有许多重複字元。删除重複字元，得以精简空间大小、增进排序速度，得到更好的资料结构：

                  build    string matching
----------------- -------- ---------------
suffix array      O(T+A)   O(PlogT)
 + lcp array      O(T+A)   O(P+logT)
suffix trie       O(T^2)   O(P)
suffix tree       O(T)     O(P)
suffix automata   O(TA)    O(P)

大量 Suffix 资料结构: Suffix Array

Suffix Array

“后缀阵列”。一个字串的全部后缀，统统放入阵列。排序所有后缀，以利之后搜寻。

一个索引值表示一个后缀。后缀阵列的空间複杂度为 O(T)。

string:
   mississippi

all suffixes:
   mississippi, ississippi, ssissippi, sissippi, issippi,
   ssippi, sippi, ippi, ppi, pi, i

suffix array:
   +---+------+---------+------------+-------------+-     -+
   | i | ippi | issippi | ississippi | mississippi |  ...  |
   +---+------+---------+------------+-------------+-     -+

suffix array:
   +---------+--------+--------+--------+-     -+
   | [10,10] | [7,10] | [4,10] | [1,10] |  ...  |
   +---------+--------+--------+--------+-     -+

suffix array:
   +----+---+---+---+---+---+---+---+---+---+---+
   | 10 | 7 | 4 | 1 | 0 | 9 | 8 | 6 | 3 | 5 | 2 |
   +----+---+---+---+---+---+---+---+---+---+---+

suffix array:
     | sa | suffix
  ---+----+------------
   0 | 10 | i
   1 |  7 | ippi
   2 |  4 | issippi
   3 |  1 | ississippi
   4 |  0 | mississippi
   5 |  9 | pi
   6 |  8 | ppi
   7 |  6 | sippi
   8 |  3 | sissippi
   9 |  5 | ssippi
  10 |  2 | ssissippi

suffix array:
   +------------------------+
   | 10 7 4 1 0 9 8 6 3 5 2 |
   +------------------------+
      i i i i m p p s s s s
        p s s i i p i i s s
        p s s s   i p s i i 
        i i i s     p s p s
          p s i     i i p s
          p s s       p i i
          i i s       p   p
            p i       i   p
            p p           i
            i p
              i

演算法（Quicksort）

以快速排序法排序所有后缀。运用内建函式库，即可轻鬆实作。每个后缀的长度都不同，名次必不同，毋须特地使用 stable sort。

两个后缀比大小需时 O(T)，两两比较次数是 O(TlogT)，时间複杂度为 O(T^2 * logT)。

大量 Suffix 资料结构: Longest Common Prefix Array

Longest Common Prefix

一堆字串的“最长共同前缀”只有一个，有可能是空字串。

演算法很简单：字串们一齐从头开始比对字元。

s1: aabbccc
s2: aabbbccc
s3: aabaccc

s1 s2 s3 的 LCP 就是 aab。

两个后缀的 LCP

string:
   abbbababba

suffixes:
   s0: abbbababba
   s1: bbbababba
   s2: bbababba
       ......
   s8: ba
   s9: a

LCP(s1, s2) = bb
LCP(s0, s9) = a

两个后缀的 LCP，
就是排序全部后缀之后，两个后缀之间的所有后缀的 LCP。

   +---------------------+
sa | 9 4 6 0 8 3 5 7 2 1 |
   +---------------------+
     0 1 2 3 4 5 6 7 8 9
    ---------------------
     a a a a b b b b b b
       b b b a a a b b b
       a b b   b b a a b
       b a b   a b   b a
       b   a   b a   a b
       a   b   b     b a
           a   a     b b
           b         a b
           b           a
           a

LCP(7th, 9th) = LCP(7th, 8th, 9th) = LCP(s7, s2, s1) = bb
LCP(4th, 8th) = LCP(4th, ..., 8th) = LCP(s8, ..., s2) = b

开头相近的后缀，排在一起；开头不相近的后缀，被开头相近的后缀隔开。

排序全部后缀之后，两个后缀之间的所有后缀的 LCP，
就是两两相邻后缀的 LCP 们的 LCP。

LCP(7th, 9th) = LCP( LCP(7th, 8th), LCP(8th, 9th) ) = bb
LCP(4th, 8th) = LCP( LCP(4th, 5th), ..., LCP(7th, 8th) ) = b

以相邻后缀的 LCP，推导出任意后缀的 LCP。

两两相邻后缀的 LCP，表达成数值：
Longest Common Prefix Array

直接记录 LCP 字串，浪费大量记忆体空间，因而改为记录 LCP 长度。辅以原字串、后缀阵列，便可得到 LCP 字串。

排序全部后缀之后，每一个后缀与前一个后缀的 LCP 长度，储存于阵列，得到 LCP Array。

     +---------------------+
  sa | 9 4 6 0 8 3 5 7 2 1 |
     +---------------------+
lcpa | 0 1 2 3 0 2 3 1 3 2 |
     +---------------------+
       0 1 2 3 4 5 6 7 8 9
      ---------------------
       a a a a b b b b b b
         b b b a a a b b b
         a b b   b b a a b
         b a b   a b   b a
         b   a   b a   a b
         a   b   b     b a
             a   a     b b
             b         a b
             b           a
             a

LCP_length(7th, 9th) = min(lcpa[7+1], ..., lcpa[9]) = 2
LCP_length(4th, 8th) = min(lcpa[4+1], ..., lcpa[8]) = 1

两个后缀的 LCP，藉由 LCP Array，变成了查询区间最小值。请参考“ 伪线段树 ”。

UVa 12338

演算法

依序计算两两相邻后缀的 LCP，依序填写 LCP Array。时间複杂度 O(T^2)。

大量 Suffix 资料结构: Suffix Trie

普通的建立方法

把一个字串的所有后缀，统统塞入一棵 Trie。

时间複杂度为 O(T^2)，空间複杂度为 O(T^2 * A)。

运用 suffix link 的建立方法

先前介绍 Aho-Corasick Algorithm 曾经提过 suffix link：每个节点各自牵一条线到次长后缀所在节点。

运用 suffix link，就能 online 建立 Suffix Trie，而且不必重覆遍历已经建立的节点。每加入一个字元，就从最深的节点开始走访 suffix link、建立新节点。

加入所有字元之后，记得标出每个后缀所在节点。

时间複杂度仍是 O(T^2)，空间複杂度仍是 O(T^2 * A)。

字串匹配

从 T 找到一个 P：从树根开始走访 Suffix Trie，看看有没有 P。时间複杂度 O(P)。

从 T 找到全部 P：建立 Suffix Trie 的时候，每个节点都必须额外记录有哪些后缀经过。

大量 Suffix 资料结构: Suffix Tree

Suffix Tree

“后缀树”是 Suffix Trie 的改良版本：

一、字串结尾添加一个从未出现的字元（例如'\0'），再来建立 Suffix Trie。如此一来，后缀结尾总是出现在树叶，不会出现在内部节点，就不必特别记录后缀所在节点。

二、去除没有分叉的节点，一串树枝合併成一根树枝。

三、树枝上的子字串，改为两个索引值、或者两个指标。

后缀树共 T+1 个树叶。字元皆相同，节点最多，共 2T+1 个节点；字元皆不同，节点最少，共 T+2 个节点。空间複杂度 O(TA)。

演算法（Ukkonen's Algorithm）

http://www.csie.ntu.edu.tw/~hil/algo2011spring/algo2011spring09.pptx

运用 suffix link，是 online 演算法，时间複杂度为 O(T+A)。

树叶终身是树叶。每次加入一个字元、要建立新节点时，不必回到最深的节点，可以从当前的节点继续。

演算法（Farach's Algorithm）

时间複杂度 O(T)。时间複杂度不含字元数量，是真正的线性时间，但是不实用，参考看看就好。

http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf

字串匹配

从 T 找到一个 P：从树根开始走访后缀树，看看有没有 P。时间複杂度 O(P)。

从 T 找到全部 P：从后缀树找到 P 之后，遍历子树。P 在 T 当中的出现次数，就是子树的叶子数量。P 在 T 当中的出现位置，就是 [ T 长度 - 叶子深度 , T 长度 - 叶子深度 + 当前节点深度 ]。

后缀树是二元树，内部节点数量等于叶子数量减一。因此子树最多 2K-1 个节点，K 是出现次数。时间複杂度 O(P+K)。

大量 Suffix 资料结构: Suffix Tray

Suffix Tray

Suffix Tree 和 Suffix Array 一併使用。

http://cs.nyu.edu/cole/papers/suffix-trays.pdf

http://courses.csail.mit.edu/6.851/spring07/scribe/lec09.pdf

大量 Suffix 资料结构: Suffix Automaton

Suffix Automaton

“后缀自动机”。把后缀通通塞入一个自动机。

http://codingsimplifylife.blogspot.tw/2016/02/sam.html

http://maskray.me/blog/2013-05-10-suffix-automaton