P3804 后缀自动机

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 2.3k | 阅读时长 ≈ 2 分钟

P3804 后缀自动机

传送门

洛谷

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

一个整数，为 所求答案

输入输出样例

输入样例#1：

abab

输出样例#1：

4

说明

对于$10\%$的数据，$\lvert S \rvert \le 1000$
对于$100\%$的数据，$\lvert S \rvert \le 10^6$

分析

既然是后缀自动机模板，自然用后缀自动机来做，具体的，就是建立后缀自动机，然后再Parent树上DFS，答案为子树大小*节点的len长度的最大值。

Update：以前没能弄清为什么siz[…]=1写在建后缀自动机里就行，写在DFS里就挂，后来Achen告诉我有些点没有siz值。

后缀自动机入门

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1000010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
struct Node
{
	int fa;
	int len;
	int ch[30];
}node[maxn<<1];
struct Edge
{
	int v;
	Edge *next;
	Edge(int a=0,Edge *b=NULL)
	{
		v=a;
		next=b;
	}
}*head[maxn<<1];
int len,tot=1,las=1;
long long ans,siz[maxn<<1];
char str[maxn];
void add(int c)
{
	int p=las,np=las=++tot;
	siz[tot]=1;
	node[np].len=node[p].len+1;
	for(;p&&!node[p].ch[c];p=node[p].fa)node[p].ch[c]=np;
	if(!p)node[np].fa=1;
	else
	{
		int q=node[p].ch[c];
		if(node[q].len==node[p].len+1)node[np].fa=q;
		else
		{
			int nq=++tot;
			node[nq]=node[q];
			node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for(;p&&node[p].ch[c]==q;p=node[p].fa)node[p].ch[c]=nq;
		}
	}
}
void dfs(int k)
{
	for(Edge *i=head[k];i!=NULL;i=i->next)
	{
		dfs(i->v);
		siz[k]+=siz[i->v];
	}
	if(siz[k]!=1)ans=max(ans,siz[k]*node[k].len);
}
int main()
{
	scanf("%s",str);
	len=strlen(str);
	for(int i=0;i<len;i++)add(str[i]-'a');
	for(int i=2;i<=tot;i++)head[node[i].fa]=new Edge(i,head[node[i].fa]);
	dfs(1);
	printf("%lld\n",ans);
    return 0;
}