后缀自动机问题

解题思路

本题要求所有子串的权值的最大值。维护一个字符串的所有子串可以用后缀自动机，而对于后缀自动机的每个状态对应的子串的出现次数其实就是他的 $endpos$ 的大小，然后乘上子串的长度，对于每个等价类中的所有字符串他的 $endpos$ 大小是相同的，要想让权值最大我们只需要取最长的一个子串的长度来更新权值，可以在递推所有 $endpos$ 的值的同时取一下最大值即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 2000010;

int tot = 1, last = 1; //tot 表示当前用到的编号，last 表示上一个点的编号，1 号点是源点（空节点）

struct Node
{
    int len, fa; //len 表示当前状态中所有子串的最大长度，fa 表示 Link 边指向的状态
    int ch[26]; //ch[i] 指向当前状态后面加上字符 i 变成的状态
}node[N]; //存储后缀自动机的每个状态
char str[N]; //原字符串
LL f[N]; //f[i] 表示后缀自动机中状态 i 的 endpos 大小
int h[N], e[N], ne[N], idx; //邻接表，用于存储所有 Link 边的反向边，便于求每个状态的 endpos 的大小
LL res; //记录答案

void extend(int c) //将字符 c 加入后缀自动机
{
    //p 表示上一个插入的状态，np 表示当前插入的新状态
    int p = last, np = last = ++tot;
    //依次加入每个点，则每次插入得到的新状态都是一个前缀，递推时无法记录前缀，这里提前算上每个前缀在 endpos 中的贡献
    f[tot] = 1;
    node[np].len = node[p].len + 1; //新状态的长度 = 旧状态的长度 + 1
    //p 的末尾加上了 c，则 p 沿着 Link 边往下走到的所有状态后面也应该都加上 c
    for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if(!p) node[np].fa = 1; //如果 p 沿着 Link 边走到的所有状态后面都没有 c，则新状态 np 的 Link 边指向源点
    else
    {
        //否则说明从当前 p 开始沿着 Link 边走到的所有状态后面都有 c，此时当前的 p 加上 c 后的状态就是一个新的等价类
        //新状态 np 的 Link 应该指向当前的 p 加上 c 后的状态 q
        int q = node[p].ch[c];
        //如果 q 的长度正好是 p 的长度 + 1，则 np 的 Link 边直接指向 q
        if(node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            //否则需要拷贝一个长度是 p 的长度 + 1 的新的状态，再令 q 和 np 的 Link 边指向拷贝后的状态 nq
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1; //拷贝并修改长度
            node[q].fa = node[np].fa = nq; //令 q 和 np 的 Link 边指向 nq
            for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq; //再将指向 q 的所有普通边改成指向 nq
        }
    }
}

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) //从源点递推所有状态的 endpos 的大小
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j); //继续往下递推
        f[u] += f[j]; //更新当前状态的 endpos 大小
    }
    if(f[u] > 1) res = max(res, f[u] * node[u].len); //如果当前状态代表的字符串出现次数不为 1，更新权值最大值
}

int main()
{
    scanf("%s", str);

    for(int i = 0; str[i]; i++) extend(str[i] - 'a'); //将每个字符依次加入后缀自动机

    memset(h, -1, sizeof h); //初始化邻接表
    //从每个状态的 Link 边指向的状态向当前状态连一条反向边
    for(int i = 2; i <= tot; i++) add(node[i].fa, i);

    dfs(1); //从源点递推所有状态的 endpos 的大小
    printf("%lld\n", res);

    return 0;
}