当初学后缀自动机的时候，找遍了全网资料，好的资料比较少
后来我弄懂了以后自己写了一篇
后缀自动机

那么放在这里分享好了

后缀自动机构造原理

程序模版

struct SAM {
    int maxlen[maxn], trans[maxn][26], link[maxn], size, last;
    SAM() {
        Set(maxlen, 0); Set(trans, 0); Set(link, 0);
        size = last = 1;
    }

    void extend(int ch) {
        //
        int cur = ++size, p = last;
        maxlen[cur] = maxlen[p] + 1;
        cnt[cur] = 1;

        for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
        if(!p) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
            else {
                int clone = ++size;
                maxlen[clone] = maxlen[p] + 1;
                Cpy(trans[clone], trans[q]); link[clone] = link[q];

                for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[cur] = link[q] = clone;
            }
        }

        last = cur;
    }
};

int main() {
    //
    freopen("input.txt", "r", stdin);
    string str;
    cin >> str;
    for(int i = 0; i < str.length(); i++) sam.extend(str[i] - 'a');

    // balabala....
}

endpos()相关性质

具体题目

看我博客文章(我还没写全，我已经工作了没那么多时间整理，不过我会尽量更新补全 )