luogu3804 【模板】后缀自动机

luogu3804 【模板】后缀自动机

​​ 题目描述 给定一个只包含小写字母的字符串 S , 请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。 输入输出格式 输入格式： 一行一个仅包含小写字母的字符串 S 输出格式： 一个整数，为 所求答案 输入输出样例 输入样例#1： 复制 abab 输出样例#1： 复制 4 说明 对于 10% 的数据， ∣S∣<=1000 对于 100% 的数据， ∣S∣<=106 拓扑排序统计出每个子串出现的个数 然后直接跑一遍统计即可

#include#include#include#define N 2200000#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline void read_s(char *s){ int op=0;char ch=gc(); while(ch<'a'||ch>'z') ch=gc(); while(ch<='z'&&ch>='a') s[op++]=ch,ch=gc();}char s[N>>1];ll ans;int len[N],fa[N],ch[N][26];int cnt=1,root=1,last=1,c[N>>1],size[N],rk[N];inline void insert1(int x){ int np=++cnt,p=last;len[np]=len[p]+1; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{ int q=ch[p][x];if(len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;fa[nq]=fa[q];memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[q]=fa[np]=nq;len[nq]=len[p]+1; for (;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } } last=np;size[np]=1;}int main(){// freopen("luogu3804.in","r",stdin); read_s(s);int ln=strlen(s); for (int i=0;i1) ans=max(ans,(ll)size[p]*len[p]); }printf("%lld\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。