YZOJ P3847 [2018省队集训]Ernd
时间限制：1000MS 内存限制：131072KB
难度：\(8.0\)
-
题目描述
给定一个长度为 \(n\) 且仅包含小写英文字母的字符串 \(S\)。你有一个字符串 \(T\)，初始为空串。
你可以进行 \(n\) 次操作，每次操作你可以在 \(T\) 的前端或末尾加入一个任意字母。记第 \(i\) 次操作后 \(T\) 在 \(S\) 中的出现次数为 \(f_i\)，你需要最大化 \(ans=\sum\limits_i f_i\) 。
-
输入格式
第一行一个正整数 \(n\) 。
第二行一个长度为 \(n\) 的字符串 \(S\) 。
-
输出格式
一行一个整数，表示 \(ans\) 的最大值。
-
样例输入
|
1 2 |
6 abcabc |
-
样例输出
|
1 |
9 |
-
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq n \leq 2\times 10^5\) 。
首先肯定 \(T\) 始终为 \(S\) 的子串答案才是最优的。
考虑在 \(T\) 前/后加一个字符的操作意味着什么。
可以发现，在 SAM 上，在 \(T\) 后加一个字符意味着沿着 ch 边往下走一个节点，在 \(T\) 前加字符意味着沿着 parent 树往上跳一个节点。
所以这个关系可以表示在 \(S\) 串的 SAM 上。
由于 SAM 是一个 DAG ，连上 parent 树的边后仍然是一个 DAG ，所以可以直接 DP。
|
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 88 89 90 |
// Powered by C4droid with GCCv7.2.0 #include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _max(_a_,_b_) ((_a_)>(_b_) ? (_a_) : (_b_)) inline void getstr(char s[],int&ls) { register char c=0; while(!(c>='a' && c<='z')) c=getchar(); ls=0; while(c>='a' && c<='z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } int cnt,parent[405050],mxval[405050],ch[405050][26],last; inline int CreateNode(register int val=0) { ++cnt,parent[cnt]=0,mxval[cnt]=val; for(register int i=0;i<26;i++) ch[cnt][i]=0; return cnt; } int right[405050]; inline int ExtendNode(register short c) { register int now=last,nw=CreateNode(mxval[last]+1); for(; now && !ch[now][c]; now=parent[now]) ch[now][c]=nw; if(!now) return parent[nw]=1,last=nw; register int q=ch[now][c]; if(mxval[q] == mxval[now]+1) return parent[nw]=q,last=nw; register int b=CreateNode(mxval[now]+1); for(register int j=0;j<26;j++) ch[b][j]=ch[q][j]; parent[b]=parent[q],parent[q]=parent[nw]=b; for(; now && ch[now][c]==q; now=parent[now]) ch[now][c]=b; return last=nw; } long long mxans,ans[405050]; int bucket[405050],lst[405050]; inline void TopoSort() { for(register int i=1;i<=cnt;i++) bucket[mxval[i]]++; for(register int i=1;i<=cnt;i++) bucket[i]+=bucket[i-1]; for(register int i=1;i<=cnt;i++) lst[bucket[mxval[i]]--]=i; for(register int i=cnt;i>=2;i--) right[parent[lst[i]]]+=right[lst[i]]; for(register int i=1;i<=cnt;i++) { register int x=lst[i],f=parent[x]; ans[x]=_max(ans[x],ans[f]+(long long)right[x]*(mxval[x]-mxval[f])); for(register int j=0,t;j<26;j++) if(t=ch[x][j]) ans[t]=_max(ans[t],ans[x]+right[t]); mxans=_max(mxans,ans[x]); } } char s[205050]; int main() { int N;scanf("%d",&N); int ls;getstr(s,ls); last=CreateNode(); for(register int i=1;i<=ls;i++) { ExtendNode(s[i]-'a'); right[last]=1; } TopoSort(); printf("%lld\n",mxans); return 0; } |