NOI2018 Day1 T3 你的名字（后缀自动机+线段树合并）
Posted On 2019年1月2日
5417: [Noi2018]你的名字
先建出原串的SAM，在线段树合并求出每个节点的Right集合
再对于每个询问在原串的SAM上求出以询问串i结尾的后缀与（原串的任意子串）重合的最大长度lim[i]
最后对于询问串建SAM，令Pos[i]为询问串的SAM节点i在询问串中的位置（任意该后缀出现的位置）
则答案为\(\sum max(0,ST[i].len-max(lim[Pos[i]],ST[ST[i].fa].len))\)
注：原题内存1G，BZOJ 只开了512M，可能需要卡内存
|
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 108 109 110 111 112 113 |
#include <iostream> #include <cstdio> #include <vector> #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=2e6+100,root=1,up=2e6; struct sam{int len,fa,trans[27];}st[maxn>>1],ST[(int)(maxn*0.9)],nul; struct seg{int lc,rc;}t[(int)((maxn<<3)*1.35)]; char s[maxn],S[maxn]; int tot,tott=1; int rt[maxn],deg[maxn>>1],q[maxn>>1],lim[maxn>>1],Pos[maxn]; inline int max(const int a,const int b){return a>b?a:b;} bool query(const int cur,const int l,const int r,const int L,const int R) { if (!cur||R<L)return 0; if (L<=l&&r<=R)return 1; int mid=(l+r)>>1;bool ans=0; if (L<=mid)ans=query(t[cur].lc,l,mid,L,R); if (!ans&&R>mid)ans|=query(t[cur].rc,mid+1,r,L,R); return ans; } int merge(int&cur,const int delta) { if (!cur||!delta)return cur=(cur|delta); t[++tot]=t[cur]; cur=tot; t[cur].lc=merge(t[cur].lc,t[delta].lc); t[cur].rc=merge(t[cur].rc,t[delta].rc); return cur; } void ins(int&cur,const int l,const int r,const int pos) { if (!cur)cur=++tot; if (l==r)return; int mid=(l+r)>>1; if (pos<=mid)ins(t[cur].lc,l,mid,pos); else ins(t[cur].rc,mid+1,r,pos); } inline void extend(sam*st,int&last,int&tott,const int ch,const int pos,const bool flag) { int np=++tott,p=last; Pos[np]=pos; if (flag)ins(rt[np],1,up,pos); st[np].len=st[p].len+1;last=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; Pos[nq]=pos; 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 build() { for (int i=2;i<=tott;i++)deg[st[i].fa]++; int front=1,rear=0; for (int i=2;i<=tott;i++) if (!deg[i])q[++rear]=i; while (front<=rear) { int cur=q[front++]; rt[st[cur].fa]=merge(rt[st[cur].fa],rt[cur]); if (!--deg[st[cur].fa]&&st[cur].fa!=root)q[++rear]=st[cur].fa; } } signed main() { scanf("%s",s+1); int n=strlen(s+1),last=1; for (int i=1;i<=n;i++)extend(st,last,tott,s[i]-'a',i,1); build(); int m=read(); for (;m;m--) { scanf("%s",s+1); int len=strlen(s+1),l=read(),r=read(),cur=root,curlen=0; ll ans=0; for (int i=1;i<=len;i++) { int ch=s[i]-'a'; if (query(rt[st[cur].trans[ch]],1,up,l+curlen,r))cur=st[cur].trans[ch],++curlen; else { while (cur!=root&&!query(rt[st[cur].trans[ch]],1,up,l+curlen,r)) if (--curlen==st[st[cur].fa].len)cur=st[cur].fa; if (query(rt[st[cur].trans[ch]],1,up,l+curlen,r))cur=st[cur].trans[ch],++curlen; } lim[i]=curlen; } int tt=1,LAST=1; for (int i=1;i<=len;i++)extend(ST,LAST,tt,s[i]-'a',i,0); for (int i=2;i<=tt;i++)ans+=max(0,ST[i].len-max(lim[Pos[i]],ST[ST[i].fa].len)); for (int i=1;i<=tt;i++)ST[i]=nul; printf("%lld\n",ans); } } |
Subscribe
0 评论