首页 > > 程序设计 > C/C++ >

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

2018-06-27 09:42:56来源：博客园阅读 ()

题目描述

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

请你求出

输入输出格式

输入格式：

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

输出格式：

一个整数，为所求答案

输入输出样例

输入样例#1：复制

abab

输出样例#1：复制

说明

对于 $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;
}