洛谷P3804 【模板】后缀自动机

题目描述

给定一个只包含小写字母的字符串 SS ,

请你求出 SS 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。

输入输出格式

输入格式：

一行一个仅包含小写字母的字符串 SS

输出格式：

一个整数，为 所求答案

输入输出样例

输入样例#1： 

abab

输出样例#1： 

4

说明

对于 10\%10% 的数据， |S|<=1000∣S∣<=1000

对于 100\%100% 的数据， |S|<=10^6∣S∣<=106

看了一天的后缀自动机，也算是入了一下门

感觉后缀自动机就是强行加各种优化压空间压时间

这题就是把后缀自动机建出来，再暴力把parent树建出来

在right集合大小*长度中取最大就好

#include<cstdio>

#include<cstring>

#include<vector>

#define LL long long

using namespace std;

const int MAXN =  * 1e6 + ;

char s[MAXN];

int N;

int last = , root = , tot = , fa[MAXN], ch[MAXN][], len[MAXN], siz[MAXN];

void insert(int x) {

    int now = ++tot, pre = last; last = now;

    //last代表全串的点

    len[now] = len[pre] + ; siz[now] = ;

    for(; pre && !ch[pre][x]; pre = fa[pre])

        ch[pre][x] = now;

    if(!pre) fa[now] = root;

    else {

        int q = ch[pre][x];//q是pre的祖先 pre -> q

        //说明pre有一条x转移边 q = pre + x

        if(len[q] == len[pre] + ) fa[now] = q;

        //说明right集合完全重合，此时pre一定是now的后缀??

        else {//right集合不完全重合

            int nows = ++tot; len[nows] = len[pre] + ;

            memcpy(ch[nows], ch[q], sizeof(ch[q]));

            fa[nows] = fa[q]; fa[q] = fa[now] = nows;

            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows;

        }

    }

}

vector<int> v[MAXN];

LL ans = ;

void dfs(int x) {

    for(int i = ; i < v[x].size(); i++)

        dfs(v[x][i]), siz[x] += siz[v[x][i]];

    if(siz[x] > ) ans = max(ans, 1ll * siz[x] * len[x]);

}

int main() {

#ifdef WIN32

    freopen("a.in", "r", stdin);

#endif

    scanf("%s", s + );

    N = strlen(s + );

    for(int i = ; i <= N; i++) insert(s[i] - 'a');

    for(int i = ; i <= tot; i++) v[fa[i]].push_back(i);

    dfs(root);

    printf("%lld", ans);

    return ;

}