洛谷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 = 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

左手用R右手Python系列之——数据框与apply向量运算

R语言与Python中的apply函数都有着丰富的应用场景,恰到好处的使用apply函数,可以避免在很多场景下书写冗余的代码,这不仅能提高代码可读性,而且提高代...

72611
来自专栏IT可乐

深入理解计算机系统(2.3)------布尔代数以及C语言运算符

  本篇博客我们主要讲解计算机中的布尔代数以及C语言的几个运算符。 1、布尔代数   我们知道二进制值是计算机编码、存储和操作信息的核心,随着计算机的发展,围绕...

2405
来自专栏从流域到海域

《笨办法学Python》 第5课手记

《笨办法学Python》 第5课手记 本节内容复习了前两节的内容,并且引入了格式化字符,这节课里的格式化字符与C语言格式化字符,规则没有什么区别。 我把原文代码...

2609
来自专栏calmound

poj 1019 Number Sequence

http://poj.org/problem?id=1019 题意:1 12 123 1234 12345 一窜数字 求第n位的数字是什么 分析:拿到题就是不会...

2743
来自专栏小白的技术客栈

Python之递归函数

Python之递归函数 好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。 Python是支持递归函数的...

3986
来自专栏有趣的Python

慕课网-C++远征之继承篇(下)-学习笔记

C++远征之继承篇(下) 多继承与多重继承 多重继承: ? 多重继承 ? 多重继承-Is-a关系 class Person { }; class Soldie...

4469
来自专栏数据结构与算法

P3371 【模板】单源最短路径

题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式: 第一行包含三个整数N、M、S,分别表示点的个数、有...

2844
来自专栏小樱的经验随笔

RMQ问题(线段树算法,ST算法优化)

RMQ (Range Minimum/Maximum Query)问题是指: 对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A...

2806
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

842
来自专栏小L的魔法馆

第十四届浙江财经大学程序设计竞赛重现赛--A-A Sad Story

2977

扫码关注云+社区

领取腾讯云代金券