BZOJ 5137: [Usaco2017 Dec]Standing Out from the Herd（广义后缀自动机）
Posted On 2019年1月2日
5137: [Usaco2017 Dec]Standing Out from the Herd
先建出广义后缀自动机，再dfs加上每个SAM上“独特”的节点对其所在串的贡献即可
|
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 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; 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=3e5+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,heavy[maxn],siz[maxn],last[maxn],cnt; int bel[maxn],ans[maxn]; char s[maxn]; inline void extend(const int ch,const int col) { int np=++tott,p=now; 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; } } if (bel[np]&&bel[np]!=col)bel[np]=-1;else bel[np]=col; } inline void add(const int a,const int b) { e[++cnt]=(zmc){b,last[a]};last[a]=cnt; } void dfs(const int cur) { for (int i=last[cur];i;i=e[i].nxt)dfs(e[i].too); if (bel[cur]&&bel[cur]!=-1)ans[bel[cur]]+=st[cur].len-st[st[cur].fa].len; if (bel[st[cur].fa]&&bel[cur]!=bel[st[cur].fa])bel[st[cur].fa]=-1; else bel[st[cur].fa]=bel[cur]; } int main() { int n=read(),ct=0; for (int i=1;i<=n;i++) { scanf("%s",s+1); int len=strlen(s+1); now=root; for (int j=1;j<=len;j++)extend(s[j]-'a',i); } for (int i=2;i<=tott;i++)add(st[i].fa,i); dfs(1); for (int i=1;i<=n;i++)printf("%d\n",ans[i]); } |
Subscribe
0 评论