【bzoj3413】匹配

我不是鸽子。

传送门

好的我没办法一句话总结出题意。

直接说吧，把模式串$T$在$S$中匹配成功的位置$pos$先求出来，然后对T的每个前缀分别计算答案。

答案由两部分组成，匹配成功的次数和失配的次数，显然如果$T$是$S$的子串，失配的次数就是$n-pos$。否则就是$n$。

对于$T$的每个前缀$i$，求出它在匹配结束前被匹配成功了几次，加起来就是匹配成功的次数。

这个东西特别难解释，但是理解了就会觉得特别好理解。。。

那么说一下操作方法，就是查询一个子串在S的某个区间里出现了几次，后缀自动机+线段树合并基本应用，关键是对于子串$i$它对应的区间是什么。由于在$[pos-len+1,pos]$这个区间内不能出现失配，所以这个区间应该是$[1,pos-len+i]$。

这个东西特别难解释，但是理解了就会觉得特别好理解。。。

说不清楚，实在不懂就去画图吧。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct SAM{
    int ch[10],len,fa;
}t1[200001];
struct tree{
    int size,ch[2];
}t2[200001*30];
char ch[100001],s[100001];
int root[200001],tot_t,tot_s=1,last=1,n,m,pos[200001];
int o[100001],a[200001],ans;
int update(int rt,int l,int r,int x){
    int u=++tot_t;
    t2[u]=t2[rt]; t2[u].size++;
    if (l==r) return u;
    int mid=(l+r)>>1;
    if (x<=mid) t2[u].ch[0]=update(t2[rt].ch[0],l,mid,x);
    else t2[u].ch[1]=update(t2[rt].ch[1],mid+1,r,x);
    return u;
}
int merge(int c,int d,int l,int r){
    if (!c||!d) return c|d;
    int u=++tot_t;
    t2[u].size=t2[c].size+t2[d].size;
    if (l==r) return u;
    int mid=(l+r)>>1;
    t2[u].ch[0]=merge(t2[c].ch[0],t2[d].ch[0],l,mid);
    t2[u].ch[1]=merge(t2[c].ch[1],t2[d].ch[1],mid+1,r);
    return u;
}
int query(int rt,int l,int r,int x){
    if (r<=x) return t2[rt].size;
    int mid=(l+r)>>1,num=query(t2[rt].ch[0],l,mid,x);
    if (x>mid) num+=query(t2[rt].ch[1],mid+1,r,x);
    return num;
}
inline void extend(int x){
    int np=++tot_s,p=last; last=np;
    t1[np].len=t1[p].len+1;
    while (p&&!t1[p].ch[x]) t1[p].ch[x]=np,p=t1[p].fa;
    if (!p) t1[np].fa=1;
    else{
        int q=t1[p].ch[x];
        if (t1[q].len==t1[p].len+1) t1[np].fa=q;
        else{
            int cp=++tot_s; t1[cp]=t1[q];
            t1[cp].len=t1[p].len+1;
            t1[q].fa=t1[np].fa=cp;
            while (p&&t1[p].ch[x]==q) t1[p].ch[x]=cp,p=t1[p].fa;
        }
    }
}
int main(){
    scanf("%d",&n); scanf("%s",ch+1);
    memset(pos,10,sizeof(pos)); pos[0]=0;
    for (int i=1; i<=n; i++){
        extend(ch[i]-'0'); pos[last]=i;
        root[last]=update(root[last],1,n,i);
    }
    for (int i=1; i<=tot_s; i++) o[t1[i].len]++;
    for (int i=1; i<=n; i++) o[i]+=o[i-1];
    for (int i=1; i<=tot_s; i++) a[o[t1[i].len]--]=i;
    int u,ed,len;
    for (int i=tot_s; i>1; i--){
        u=a[i];
        pos[t1[u].fa]=min(pos[t1[u].fa],pos[u]);
        root[t1[u].fa]=merge(root[t1[u].fa],root[u],1,n);
    }
    scanf("%d",&m);
    while (m--){
        scanf("%s",s+1); len=strlen(s+1);
        u=1;
        for (int i=1; i<=len&&u; i++)
            u=t1[u].ch[s[i]-'0'];
        ed=pos[u]; u=1; ans=0;
        for (int i=1; i<=len; i++){
            u=t1[u].ch[s[i]-'0'];
            if (!u) break;
            if (!ed) ans+=query(root[u],1,n,n);
            else ans+=query(root[u],1,n,ed+i-len);
        }
        if (!ed) ans+=n;
        else ans+=ed-len;
        printf("%d\n",ans);
    }
    return 0;
}