BZOJ3413: 匹配（后缀自动机，Parent树，线段树合并）

Description

Input

第一行包含一个整数n(≤100000)。

第二行是长度为n的由0到9组成的字符串。

第三行是一个整数m。

接下来m≤5·10行，第i行是一个由0到9组成的字符串s，保证单行字符串长度小于等于10^5，所有字符串长度和小于等于3·10^6

Output

输出m行，第i行表示第si和S匹配所比较的次数。

Sample Input

7
1090901
4
87650
0901
109
090

Sample Output

7
10
3
4

解题思路：

卡了我一天，我好弱啊

这道题需要在思路上做出一步转化，将分配次数分配到每个点上。

话句话说，假如说在模板串i位上匹配了f[i]次，那么答案就是sigma(f[i])。

那么就要求我们求出在每一位上的f[i]的值。

f[i]=在i上失配次数+在i上匹配成功次数，其中失配次数可以单独处理出来。

如果匹配永远不会成功，那么，我们可以知道，失配次数一定是n。

如果匹配在某一位成功，那么失配次数就是左端点右移次数。

那么成功次数呢？

可知，在完成匹配之后的部分，是不产生贡献的。

那么结果就是在一个Parent节点子树内的结束节点。

所以我们就需要维护一个集合，集合内包含所有Parent节点子树内的endpos。

这部分用线段树就好了，向上合并。

查询个数时只需要确定好上限。

查询结束位置时只需要进行后缀自动机匹配即可，记录最后一个节点并保证未失配。

再进行第二次匹配，只需要限制其上限，在线段树中查询个数就好了。

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 const int N=200005;
  5 const int S=500005;
  6 typedef long long lnt;
  7 struct sant{
  8     int tranc[26];
  9     int len;
 10     int pre;
 11 }s[S];
 12 struct pnt{
 13     int hd;
 14     int root;
 15 }p[S];
 16 struct trnt{
 17     int ls;
 18     int rs;
 19     int sum;
 20 }tr[S<<3];
 21 int cnt;
 22 int siz;
 23 int fin;
 24 int n,Q;
 25 int top;
 26 int size;
 27 char tmp[N];
 28 int topo[S];
 29 int has[S];
 30 int t;
 31 void pushup(int spc)
 32 {
 33     tr[spc].sum=tr[tr[spc].ls].sum+tr[tr[spc].rs].sum;
 34     return ;
 35 }
 36 int hav(int l,int r,int spc,int pos)
 37 {
 38     if(!spc)
 39         return 0;
 40     if(l==r)
 41         return l;
 42     int mid=(l+r)>>1;
 43     if(pos<=mid)
 44         return hav(l,mid,tr[spc].ls,pos);
 45     else
 46         return hav(mid+1,r,tr[spc].rs,pos);
 47 }
 48 void update(int l,int r,int &spc,int pos)
 49 {
 50     
 51     if(!spc)
 52         spc=++size;
 53     tr[spc].sum++;
 54     if(l==r)
 55         return ;
 56     int mid=(l+r)>>1;
 57     if(pos<=mid)
 58         update(l,mid,tr[spc].ls,pos);
 59     else
 60         update(mid+1,r,tr[spc].rs,pos);
 61     return ;
 62 }
 63 int Merge(int spcf,int spcs)
 64 {
 65     if(!spcf||!spcs)
 66         return spcf+spcs;
 67     int spc=++size;
 68     tr[spc].sum=tr[spcf].sum+tr[spcs].sum;
 69     tr[spc].ls=Merge(tr[spcf].ls,tr[spcs].ls);
 70     tr[spc].rs=Merge(tr[spcf].rs,tr[spcs].rs);
 71     return spc;
 72 }
 73 int Minpos(int l,int r,int spc)
 74 {
 75     if(l==r)
 76         return l;
 77     int mid=(l+r)>>1;
 78     if(tr[tr[spc].ls].sum)
 79         return Minpos(l,mid,tr[spc].ls);
 80     else
 81         return Minpos(mid+1,r,tr[spc].rs);
 82 }
 83 lnt query(int l,int r,int spc,int lim)
 84 {
 85     if(l>lim||!spc)
 86         return 0;
 87     if(l==r||r<=lim)
 88         return tr[spc].sum;
 89     int mid=(l+r)>>1;
 90     return query(l,mid,tr[spc].ls,lim)+query(mid+1,r,tr[spc].rs,lim);
 91 }
 92 void Insert(int c,int plc)
 93 {
 94     t=plc;
 95     int nwp,nwq,lsp,lsq;
 96     nwp=++siz;
 97     s[nwp].len=s[fin].len+1;
 98     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)
 99         s[lsp].tranc[c]=nwp;
100     if(!lsp)
101         s[nwp].pre=1;
102     else{
103         lsq=s[lsp].tranc[c];
104         if(s[lsq].len==s[lsp].len+1)
105             s[nwp].pre=lsq;
106         else{
107             nwq=++siz;
108             s[nwq]=s[lsq];
109             s[nwq].len=s[lsp].len+1;
110             s[lsq].pre=s[nwp].pre=nwq;
111             while(s[lsp].tranc[c]==lsq)
112             {
113                 s[lsp].tranc[c]=nwq;
114                 lsp=s[lsp].pre;
115             }
116         }
117     }
118     fin=nwp;
119     update(1,n,p[fin].root,plc);
120     return ;
121 }
122 int main()
123 {
124     fin=++siz;
125     scanf("%d",&n);
126     scanf("%s",tmp+1);
127     for(int i=1;i<=n;i++)
128         Insert(tmp[i]-'0',i);
129     for(int i=1;i<=siz;i++)
130         has[s[i].len]++;
131     for(int i=1;i<=siz;i++)
132         has[i]+=has[i-1];
133     for(int i=1;i<=siz;i++)
134         topo[has[s[i].len]--]=i;
135     for(int i=siz;i;i--)
136     {
137         int x=topo[i];
138         if(x==1)
139             continue;
140         p[s[x].pre].root=Merge(p[s[x].pre].root,p[x].root);
141     }
142     scanf("%d",&Q);
143     while(Q--)
144     {
145         scanf("%s",tmp+1);
146         int len=strlen(tmp+1);
147         int root=1;
148         int endpos=0x3f3f3f3f;
149         lnt ans=0;
150         for(int i=1;i<=len;i++)
151             root=s[root].tranc[tmp[i]-'0'];
152         if(!root)
153             ans=n;
154         else{
155             endpos=Minpos(1,n,p[root].root);
156             ans=endpos-len;
157         }
158         root=1;
159         for(int i=1;i<=len;i++)
160         {
161             int c=tmp[i]-'0';
162             root=s[root].tranc[c];
163             int tmp=ans;
164             if(root)
165                 ans+=query(1,n,p[root].root,endpos+i-len);
166             else
167                 break;
168         }
169         printf("%lld
",ans);
170     }
171     return 0;
172 }