SAM.cpp

struct SAM {
    struct nd { int l, p; array<int, 26> e; };
    vector<nd> v;
    SAM() : v(2, nd{0, 0, {0}}) {}
    void push(int c) {
        int wh = v.size(), st = wh - 1, it = st;
        while (it && !v[it].e[c]) it = v[it].p;
        if (it && v[v[it].e[c]].l != v[it].l + 1) {
            int cp = wh++, ob = v[it].e[c];
            v.push_back(nd{v[it].l + 1, v[ob].p, v[ob].e});
            for (v[ob].p = cp; it && v[it].e[c] == ob; it = v[it].p) v[it].e[c] = cp;
        }
        for (it = st; it && !v[it].e[c]; it = v[it].p) v[it].e[c] = wh;
        v.push_back(nd{v[st].l + 1, it ? v[it].e[c] : 1, v[0].e});
    }
};