//我真的没有口吃，标题里的第一个后缀自动机是题目名称，第二个是解决问题用的算法

1. 题目

2. 题解

OvO 模板题做到要崩溃

好吧不吐槽了

自动机上每个点对应了一个 $endpos$ 集合，也对应了一个字符串集合 $S$ ，集合 $S$ 里的字符串在原串中的结尾位置都在且仅在 $endpos$ 集合中

因此我们只需要维护 $|endpos|$ （ $endpos$ 集合大小）和 $S$ 中最长字符串长度。

答案就是对于 $|endpos| > 1$ 的点，它们的 $|endpos|\times maxlen$ 的最大值

具体就是在 $pre$ 树上 Dp 一波， $pre$ 树上的点对应的 $endpos$ 就是其树上儿子的 $endpos$ 的并（实际上 $pre$ 树上的兄弟的 $endpos$ 集合并不会有交集，因为 $endpos$ 有交集说明其中一个是另一个的后缀，那么它们在 $pre$ 树上应当是父（祖先）子关系）

然后插入的时候每个新插入的那 $n$ 个点本身初始 $endpos$ 大小为 1（因为它在插入时是当前最长的字符串）

再树型 Dp 计算一下子树 $size$ 就行了

具体看代码吧，还是比较简单的。。。

我一开始是对 SAM 认知不足，以为新插入的那 $n$ 个点就是 $pre$ 树的叶子节点。。。然而其实并不是。。。比如插入的字符串是 aba，其中第一个 a 所代表的节点就不是叶子节点。。。

#include <bits/stdc++.h>

#define NS (2000005)

using namespace std;

typedef long long LL;

struct GRAPH
{
    int head[NS], nxt[NS], to[NS], sz;
    GRAPH() {memset(head, -1, sizeof(head)), sz = 0;}
    void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

struct SAM
{
    struct N
    {
        int nxt[26], pre, mxl, sz;
        int& operator [] (const int a) {return nxt[a];}
    } e[NS];
    int lst, sz;
    SAM() {lst = sz = 1;}
    void insert(int c)
    {
        int a = ++sz, b = lst; lst = a, e[a].mxl = e[b].mxl + 1, e[a].sz = 1;
        while (b && !e[b][c]) e[b][c] = a, b = e[b].pre;
        if (!b) {e[a].pre = 1; return;}
        int q = e[b][c];
        if (e[q].mxl == e[b].mxl + 1) e[a].pre = q;
        else
        {
            int nq = ++sz; e[nq] = e[q], e[nq].mxl = e[b].mxl + 1, e[nq].sz = 0;
            e[nq].pre = e[q].pre, e[q].pre = e[a].pre = nq;
            while (e[b][c] == q) e[b][c] = nq, b = e[b].pre;
        }
    }
} sam;

char s[NS];

int n;

LL mx;

void Dfs(int a)
{
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        Dfs(g[i]), sam.e[a].sz += sam.e[g[i]].sz;
    if (sam.e[a].sz != 1) mx = max(mx, 1ll * sam.e[a].mxl * sam.e[a].sz);
}

int main(int argc, char const* argv[])
{
    scanf("%s", s), n = strlen(s);
    for (int i = 0; i < n; i += 1) sam.insert(s[i] - 'a');
    for (int i = 2; i <= sam.sz; i += 1) g.push(sam.e[i].pre, i); 
    Dfs(1), printf("%lld\n", mx);
    return 0;
}

【题解】【模板】后缀自动机后缀自动机 LUOGU – 3804

于2018年8月25日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】【模板】后缀自动机 后缀自动机 LUOGU – 3804

于2018年8月25日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题解】【模板】后缀自动机后缀自动机 LUOGU – 3804

发表回复取消回复