BZOJ 3238: [Ahoi2013]差异（后缀自动机）
Posted On 2019年1月2日
3238: [Ahoi2013]差异
求LCP，反向建SAM，任意以两点i,j为后缀的字符串（原串）的LCP即反串的Parent树的LCA
再推一波总方案数减去即可（你要暴力求也行）
|
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 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define int long long typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e6+100; struct sam{int len,fa,trans[27];}st[maxn]; struct zmc{int too,nxt;}e[maxn<<1]; int tott=1,now=1,root=1,tot,siz[maxn],last[maxn],cnt; ll ans; char s[maxn]; inline void extend(const int ch) { int np=++tott,p=now;siz[tott]=1; st[np].len=st[p].len+1;now=np; while (p&&!st[p].trans[ch])st[p].trans[ch]=np,p=st[p].fa; if (!p)st[np].fa=root; else { int q=st[p].trans[ch]; if (st[p].len+1==st[q].len)st[np].fa=q; else { int nq=++tott; st[nq]=st[q]; st[nq].len=st[p].len+1; st[np].fa=st[q].fa=nq; while (p&&st[p].trans[ch]==q)st[p].trans[ch]=nq,p=st[p].fa; } } } inline void add(const int a,const int b) { e[++cnt]=(zmc){b,last[a]};last[a]=cnt; } ll sum[maxn]; void dfs(const int cur) { for (int i=last[cur];i;i=e[i].nxt) { dfs(e[i].too); ll tmp=st[cur].len; ans+=1ll*siz[e[i].too]*siz[cur]*tmp; siz[cur]+=siz[e[i].too]; } } signed main() { scanf("%s",s+1); int n=strlen(s+1); ll aw=1ll*(n-1)*(1+n)*n/2; for (int i=n;i;i--)extend(s[i]-'a'); for (int i=1;i<=tott;i++)add(st[i].fa,i); siz[1]=1; dfs(1); printf("%lld\n",aw-ans*2); } |
Subscribe
0 评论