欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-24 13:08:12
题目描述 给定一个只包含小写字母的字符串 SS , 请你求出 SS 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。 输入输出格式 输入格式: 一行一个仅包含小写字母的字符串 SS 输出格式: 一个整数,为 所求答案 输入输出样例 输入样例#1: 复制 abab 输出样例#1: 复 ......

题目描述

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

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

输入输出格式

输入格式:

 

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

 

输出格式:

 

一个整数,为 所求答案

 

输入输出样例

输入样例#1: 复制
abab
输出样例#1: 复制
4

说明

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

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

 

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

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

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

在节点大小*长度中取最大就好

 

#include<cstdio>
#include<cstring>
#include<vector>
#define LL long long 
using namespace std;
const int MAXN = 2 * 1e6 + 10;
char s[MAXN];
int N;
int last = 1, root = 1, tot = 1, fa[MAXN], ch[MAXN][26], len[MAXN], siz[MAXN];
void insert(int x) {
    int now = ++tot, pre = last; last = now;
    //last代表全串的点 
    len[now] = len[pre] + 1; siz[now] = 1;
    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] + 1) fa[now] = q;
        //说明right集合完全重合,此时pre一定是now的后缀??
        else {//right集合不完全重合 
            int nows = ++tot; len[nows] = len[pre] + 1;
            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 = 0;
void dfs(int x) {
    for(int i = 0; i < v[x].size(); i++)
        dfs(v[x][i]), siz[x] += siz[v[x][i]];
    if(siz[x] > 1) ans = max(ans, 1ll * siz[x] * len[x]);
}

int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    scanf("%s", s + 1);
    N = strlen(s + 1);
    for(int i = 1; i <= N; i++) insert(s[i] - 'a');
    for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i);
    dfs(root);
    printf("%lld", ans);
    return 0;
}