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

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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *