广义后缀自动机

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
namespace suffix_automata{
    int maxlen[maxn], trans[maxn][26], link[maxn], size = 1;
//    int sizes[maxn], ru[maxn];
    inline int insert(int ch, int last){
        ch -= 'a';
        if(trans[last][ch]){
            int p = last, x = trans[p][ch];
            if (maxlen[p] + 1 == maxlen[x]){
//              sizes[x] = 1;
                return x;
            }else{
                int y = ++size;
                maxlen[y] = maxlen[p] + 1;
                for (int i = 0; i < 26; ++i)
                    trans[y][i] = trans[x][i];
                while (p && trans[p][ch] == x)
                    trans[p][ch] = y, p = link[p];
                link[y] = link[x], link[x] = y;
//                sizes[y] = 1;
                return y;
            }
        }
        int z = ++size, p = last;
        maxlen[z] = maxlen[last] + 1;
        while (p && !trans[p][ch])
            trans[p][ch] = z, p = link[p];
        if (!p)
            link[z] = 1;
        else{
            int x = trans[p][ch];
            if (maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                int y = ++size;
                maxlen[y] = maxlen[p] + 1;
                for (int i = 0; i < 26; ++i)
                    trans[y][i] = trans[x][i];
                while (p && trans[p][ch] == x)
                    trans[p][ch] = y, p = link[p];
                link[y] = link[x], link[z] = link[x] = y;
            }
        }
//        sizes[z] = 1;
        return z;
    }
    ll cal(){
        ll ans = 0;
//        queue<int>Q;
//        for(int i = 2; i <= size; ++i) ++ru[link[i]];
//        for(int i = 1; i <= size; ++i){
//          if(!ru[i])  Q.push(i);
//      }
//        while(!Q.empty()){
//            int x = Q.front();
//          Q.pop();
//            sizes[link[x]] += sizes[x];//分开更新
//            if(!(--ru[link[x]]))  Q.push(link[x]);
//        }
        for(int i = 2; i <= size; i++)   ans += maxlen[i] - maxlen[link[i]];
        return ans;
    }
};