It's written in 2016,and I just carry it from another blog(zybuluo) of mine.

正文：

后缀自动机是一种可以识别一个字符串所有后缀的自动机.
简单地总结一下：
众所周知，在自动机上移动的过程就是识别字符串的过程，
设\(ST(a)\)表示从a状态开始能够识别的所有后缀，那么这些后缀都有一个\(ST(a)\)的公共前缀，对于状态a代表的可能字串长度是一段连续的区间，不妨设其为\([\min(a),\max(a)]\).
update:"识别"的意思是从状态a开始在自动机上输入一个后缀能够到达某一个终点（识别成功）,那么就说状态a能够识别这个后缀.（状态a也是从初始状态输入若干字符得到的）
举例:设串A=abcabde,那么{ab}能够识别的后缀为{suffix(2),suffix(5)},而{a}能够识别{suffix(1),suffix(4)},两者能够识别的后缀完全不同.

设a能够识别的所有后缀集合为\(right(a)\),将这些后缀编号为\(r_1,r_2,…,r_m\),(r是后缀下标)，那么\(right(a)={r_1,…,r_m}\).
一个例子：
aabbaabbabba
对于状态a={abb},它能识别的后缀有
\(\;\;\)aabbabba
\(\;\;\;\;\;\;\;\;\) abba
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\) a
对于right集合{4,8,11},它对应的可能状态为{abb,bb},那么a的可能长度为[2,3].
注意，当这段长度超过范围时right集合也会变化，
比如对于状态{aabb}对应right集合为{4,8}.

2.实际上,parent树中结点不一定都有多于1个儿子,有时只有一个儿子,比如串aa;可能合理的解释是后缀下标较小的那个在自动机中的末尾结点与父结点合并了,或者说从父结点往后继续匹配只能匹配一个儿子,另一个已经完成.

可以证明right集合和一个状态是一一对应的.
同时可以证明两个状态a,b的right集合要么不相交，要么一个是另一个真子集，
反证，设他们交集为\({r_i}\),首先\([\min(a),\max(a)]\)和\([\min(b),\max(b)]\)一定没有交集，否则a的后缀b一定能取到;
设\(\max(a)<\min(b) \),那么对于交集，a能够取到的串b也一定能够取到，那么对于所有right(a),b也一定能够取到，所以\(right(a) \subset right(b)\).
也可以这样想，从null开始，我们逐渐向前加入字符，right(a)的范围也在不断缩小，且对于不同的字符，right集合划分也不一样.
最后直到|right(a)|=1, 此时完全与某一个后缀识别；
按right集合的包含关系容易构出一棵parent树(取n=5,灵魂画图)：
\(\;\)
\( \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \) (1,2,3,4,5)
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) / \(\;\;\;\;\;\;\;\;\;\) \
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) (1,2,3) \(\;\;\;\;\;\;\;\;\)(4,5)
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) / \(\;\;\;\;\;\) \ \(\;\;\;\;\;\;\;\;\;\;\) | \(\;\;\) \
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) (1) \(\;\;\;\;\;\;\) (2,3) \(\;\;\;\;\) (4) \(\;\) (5)
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) / \(\;\;\;\) \
\(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\) (2) \(\;\;\;\;\) (3)

从整棵树来看，根的right集合为全集，字符为null；加入字符a/b/...,得到首字母前一位为a/b/...的后缀right集合，且向前加入字符越多，right集合越小。你可能已经发现了，这很像一棵后缀trie；我们可以将一个点和它parent之间的边赋上长度=区间大小，比如上面例子：长度([2,3])=2,parent=状态{b},本状态{abb,bb},则可视为该边有字符串"ab",类似地,该点有两个儿子,对应边"a"(+abb)right{4,8}和"aabbaabb"(+abb)right{11}，注意到后缀11只有一个后缀了，故可能的字符串可以一直延伸到开头。
这样，parent树从根到叶子的一条路径就是从某一点出发倒着排列字符一直排到开头，换而言之，将原字符串倒序后建立parent树就是原串的后缀树，这也为线性建后缀树提供了一种相当方便的方式。

注意，在原版后缀树中，如果不对原串末尾加特殊字符，可能会出现后缀1是后缀2的前缀，且恰好在后缀2的一条边上导致该后缀消失的情况，而在自动机构建的后缀树上，对这种情况会在边上额外建立一个点表示后缀1，从而打破了每个非叶节点至少有两个分支的规律（当然点数还是o(n)的.）.
同样，从后缀树的规律我们可以得到其他性质：
min(i)=max(fa(i))+1；
由于是自动机，一个子串唯一对应一个状态;
由于每个结点至少有2个叶结点（否则这两个结点会缩为一个点，就是[min(a),max(a)]的表示），所以总点数是o(n)的.
边数也容易证明o(n),此处省略;
...

update:
一个状态a的parent结点b可以形象地看作是a的可能长度不断缩小,即右端点不变,左端点右移,（如果右端点左移,那么显然不能与当前right集合的后缀匹配了)直到有更多的后缀能够被当前长度识别,
如:对于串A=abcabcbcdcc,状态a{abc}能够识别{3,6};右移得到{bc},能够识别{3,6,8};右移得到{c},能够识别{3,6,8,10}.
所以可以得出几个性质:
若状态a可以对应串t,那么|right(a)|=t在原串中出现次数;
状态a向parent指针移动,可以看作寻找合适匹配(详见最长公共字串);

构造方法直接贴代码：

#define go(x,i) a[x].ch[i]
#define fa(x) a[x].parent
#define lm(x) a[x].mr
#define mi(x) a[x].ml
using namespace std;

struct node{
    int ch[27];
    int parent,ml,mr;
    node() {memset(ch,0,sizeof(ch)); parent=ml=mr=0;}
}a[nn];
char s[nn];

void add(int p,int len)
{
    int q,np=++cnt,x=s[len]-'a'+1;
    for(;p&&!go(p,x);p=fa(p)) go(p,x)=np;
    if(!p) fa(np)=0;
    else
    {
        q=go(p,x);
        if(lm(q)==lm(p)+1) fa(np)=q;
        else
        {
            int nq=++cnt;
            for(int i=1;i<=26;++i) go(nq,i)=go(q,i);
            fa(nq)=fa(q); fa(q)=nq; fa(np)=nq;
            lm(nq)=lm(p)+1;
            for(;p&&go(p,x)==q;p=fa(p)) go(p,x)=nq;
        }
    }
    last=np;
    lm(last)=len+1;
}

void init()
{
    scanf("%s",s);
    n=strlen(s);
    cnt=0; last=1;
    for(int i=0;i< n;++i) add(last,i);
    for(int i=1;i<=cnt;++i) mi(i)=ml(fa(i))+1;
}