BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster（伪广义后缀自动机+DSU On Tree）
Posted On 2019年1月2日
2780: [Spoj]8093 Sevenk Love Oimaster
先对模板串建SAM（看作同一串，串间加分隔符）
对Parent树跑DSU On Tree得出每个节点的答案
最后再对每个询问跑一遍SAM即可
注意是全串匹配！匹配时别跳fa边
|
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#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=400000+100,inf=1e9,up=10000; 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,bel[maxn],aw[maxn]; int sum[maxn],AW; char s[maxn]; inline int max(const int a,const int b){return a>b?a:b;} inline int min(const int a,const int b){return a<b?a:b;} void ins(const int pos,const int delta) { if (delta==1) { if (!sum[pos])sum[pos]=1,++AW; } else AW=0,sum[pos]=0; } inline void extend(const int ch,const int col) { int np=++tott,p=now; bel[np]=col; 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; bel[nq]=col; 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; } void dfs(const int cur) { siz[cur]=1; for (int i=last[cur];i;i=e[i].nxt) dfs(e[i].too),siz[cur]+=siz[e[i].too],siz[heavy[e[i].too]]>siz[heavy[cur]]&&(heavy[cur]=e[i].too); } int skip; void cal(const int cur,const int delta) { ins(bel[cur],delta); for (int i=last[cur];i;i=e[i].nxt) if (e[i].too!=skip)cal(e[i].too,delta); } void dsu(const int cur,const bool h) { if (heavy[cur])dsu(heavy[cur],1); for (int i=last[cur];i;i=e[i].nxt) if (e[i].too!=heavy[cur])dsu(e[i].too,0); skip=heavy[cur]; cal(cur,1); aw[cur]=AW; skip=0; if (!h)cal(cur,-1); } int main() { int n=read(),q=read(); for (int i=1;i<=n;i++) { scanf("%s",s+1); int len=strlen(s+1); for (int j=1;j<=len;j++)extend(s[j]-'a',i);extend(26,i); } for (int i=1;i<=tott;i++)add(st[i].fa,i); dfs(1); dsu(1,1); while (q--) { scanf("%s",s+1); int cur=root,len=strlen(s+1); for (int i=1;i<=len;i++) { int ch=s[i]-'a'; if (!st[cur].trans[ch]) { cur=root; break; } if (st[cur].trans[ch])cur=st[cur].trans[ch]; } printf("%d\n",cur==root?0:aw[cur]); } } |
Subscribe
0 评论