题目描述
给定一个只包含小写字母的字符串SS,
请你求出 SS 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。
先讲讲对后缀自动机的理解:
后缀自动机就是后缀树倒过来的样子,很形象.
如ACADD:
其构造的思想大致是：
1.首先将点分为一些类别，其中有一些是接受点，也就是说走到接受点的都是原串的后缀，而接受点不止一个，所有的接受点就组成了所有后缀的集合.
2.当新加入一个字母c，那么原串的结尾就会产生变化，也就是说接受点要发生改变，我们就要想办法将当前的接受点的集合转移成新的集合，因为后缀自动机要保证状态数最小化，所以我们要尽量利用以前的状态来产生新的状态，所以当他的父亲节点含有c这个转移时，我们就直接讨论能否直接利用即可，注意：这里的父亲是指接受点集合之间的关系，也就是说沿着父亲节点走依旧会是接受点.
他的构造处有一些难理解的地方,比如len[q]==len[p]+1 和 len[q]>len[p]+1的讨论
如此图中
如此图中,在构造第二个A时 起始p为C 然后跳到了root 构造A时由于len[q]==len[p]+1 (p为root,q为第一处的A)那么就直接把A接到C后面，因为这种情况下q的路径必然经过p,可以脑补一下.
另一种就是插入D时 len[q]>len[p]+1 的情况,可以简单的想想,如果直接把D接到q指针的D后面,那么DD这个后缀将无法走出
所以要新建一个D强行满足第一种情况,就可以满足条件了
按这个例子的理解:如果len[q]!=len[p]+1 那么p-q中间存在一条路径,且只有这条路径上的点可以直接到达D.那么就会漏掉一些后缀.
严格的理解：
因为我们的目标是做到状态的最小化，所以要尽量利用之前的状态，那么如果len[q]==len[p]+1，那么就可以直接利用.
如果len[q]>len[p]+1，一个状态接受的字符串的长度是连续的，那么p-q之间还存在其他更长的后缀，我们要保证在新的后缀建立的情况下，原来的状态不能丢失，所以要新建节点，产生两个分支，这也是要把q复制到新节点上的原因，q能走到的地方，新节点都能走到，此时q的作用就是接受之前更长的子串.
重要性质:
1.设当前点为p,那么fa[p]是以p结尾的字符串的集合的最大子集,且不重复(根据构建方法可以脑补)
2.每一个节点内代表的字符串的长度是一段连续的区间[minlen,maxlen],且 maxlen[fa]+1=minlen
利用这个性质就可以解决这题,可以在parent树上直接dp,fa[p]存在的串,p也一定存在,那么就可以直接累加了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long ll; 9 const int N=1e6+5,M=2e6+10;10 char s[N];int cur=1,cnt=1,n,last,ch[M][27],fa[M],dis[M],size[M];ll ans=0;11 void build(int c,int id){12 last=cur;cur=++cnt;13 int p=last;dis[cur]=id;14 for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;15 if(!p)fa[cur]=1;16 else{17 int q=ch[p][c];18 if(dis[q]==dis[p]+1)fa[cur]=q;19 else{20 int nt=++cnt;dis[nt]=dis[p]+1;21 memcpy(ch[nt],ch[q],sizeof(ch[q]));22 fa[nt]=fa[q];fa[q]=fa[cur]=nt;23 for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;24 }25 }26 size[cur]=1;27 }28 int c[N],sa[M];29 void flower(){30 for(int i=1;i<=cnt;i++)c[dis[i]]++;31 for(int i=1;i<=n;i++)c[i]+=c[i-1];32 for(int i=cnt;i>=1;i--)sa[c[dis[i]]--]=i;33 for(int i=cnt;i;i--){34 int p=sa[i];35 if(size[p]>1)ans=max(ans,(ll)size[p]*dis[p]);36 size[fa[p]]+=size[p];37 }38 }39 void work(){40 scanf("%s",s+1);n=strlen(s+1);41 for(int i=1;i<=n;i++)build(s[i]-'a',i);42 flower();43 printf("%lld\n",ans);44 }45 int main()46 {47 work();48 return 0;49 }