特征

1、对于每个节点，父节点的接受串是该节点的接受串的后缀，而且是最长的那个。用该节点的len减去父节点的fa.len，就是该节点表示的串中父节点不能表示的串个数。

同理，当插入这个节点，出现的新不同子串个数就是len-fa.len。

2、每个节点表示串出现的次数，是这个节点子树上有效节点的总数。（有效节点指插入该字符产生的那个节点，也就是代码中extend中的clone节点）。

这样我们初始化有效节点为1，然后拓扑排序dp，就可以O(n)得到每个节点出现次数。

3、后缀自动机是一张有向无环图，其中顶点是状态，而边代表了状态之间的转移。

4、任意路径“匹配”某一子串，该子串由路径中边的标记组成。

5、如果程序中所处理字符串的最大可能长度是MAXN，那么至多会占用2*MAXN-1个状态。

6、由长度为n的字符串s建立的后缀自动机中，转移的数量不超过3n-4（对于n>=3）。

模板

1 #include
      
         2 #include
       
          3 using namespace std;  4 const int maxn = 1e5 + 10;  5 struct node  6 {  7     int ch[26], par,len;  8 }SA[maxn*2];  9 int sz, root, last; 10 void init() 11 { 12     sz = root = last = 0; 13     SA[0].len = 0; 14     SA[0].par = -1; 15     memset(SA[0].ch, 0, sizeof(SA[0].ch)); 16 } 17  18 void extend(int c) 19 {
    //向当前字符串的尾部添加一个字符 20     int p = last, cur = ++sz; 21     SA[cur].len = SA[p].len + 1; 22     for (; p!=-1 && !SA[p].ch[c]; p = SA[p].par) SA[p].ch[c] = cur; 23     if (p == -1) SA[cur].par = root; 24     else 25     { 26         int q = SA[p].ch[c]; 27         if (SA[q].len == SA[p].len + 1) SA[cur].par = q; 28         else 29         { 30             int clone = ++sz; 31             SA[clone] = SA[q]; 32             SA[clone].len = SA[p].len + 1; 33             SA[q].par = SA[cur].par = clone; 34             for (; p != -1 && SA[p].ch[c] == q; p = SA[p].par) SA[p].ch[c] = clone; 35         } 36     } 37     last = cur; 38 } 39 int encode(char c) 40 { 41     return c - 'a'; 42 } 43 int Count_substrings() 44 {
    //不同子串的个数 45     int ans = 0; 46     for (int i = 1; i <= sz; i++) 47     { 48         ans += SA[i].len - SA[SA[i].par].len; 49     } 50     return ans; 51 } 52 bool find_substring(int*des, int n) 53 {
    //寻找子串是否存在 54     int i=0, cur = SA[root].ch[des[0]]; 55     while (i < n&&cur) 56     { 57         i++; 58         cur = SA[cur].ch[des[i]]; 59     } 60     if (i == n) return true; 61     else return false; 62 } 63 int r[maxn<<2],w[maxn]; 64 void RadixSort(int n) 65 {
    //拓扑排序 66     for(int i=0;i<=n;i++) w[i]=0;  67     for(int i=1;i<=sz;i++) w[SA[i].len]++; 68     for(int i=1;i<=n;i++) w[i]+=w[i-1]; 69     for(int i=sz;i>=1;i--) r[w[SA[i].len]--]=i; 70     r[0]=0; 71 } 72 int LCS(int*P,int lenP) 73 {
    //求串P与建立后缀自动机的串的最长公共子串 74     int lcs=0,now=0,ans=0; 75     for(int i=0;i