[BZOJ3413]匹配

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

Solution

又一道码农题...

后缀自动机上线段树合并求出每个点的\(endpos\)集合的位置，然后拿串在\(SAM\)上面跑，随便乱搞一下就好了。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

const int maxn = 2e5+10;

int n,m,rt[maxn],sgt;
char s[maxn];

#define mid ((l+r)>>1)

struct Segment_Tree {
    int ls[maxn*30],rs[maxn*30],t[maxn*30];

    void modify(int &p,int l,int r,int x) {
        if(!p) p=++sgt;t[p]++;
        if(l==r) return ;
        if(x<=mid) modify(ls[p],l,mid,x);
        else modify(rs[p],mid+1,r,x);
    }

    int query(int p,int l,int r,int x,int y) {
        if(!p) return 0;
        if(x<=l&&r<=y) return t[p];
        int ans=0;
        if(x<=mid) ans+=query(ls[p],l,mid,x,y);
        if(y>mid) ans+=query(rs[p],mid+1,r,x,y);
        return ans;
    }

    int merge(int x,int y) {
        if(!x||!y) return x+y;
        int p=++sgt;
        t[p]=t[x]+t[y];
        ls[p]=merge(ls[x],ls[y]);
        rs[p]=merge(rs[x],rs[y]);
        return p;
    }
}SGT;

struct Suffix_Automaton {
    int qs,lstp,cnt;
    int tr[maxn][10],par[maxn],ml[maxn],t[maxn],r[maxn],vis[maxn],pos[maxn];

    void clear() {qs=lstp=cnt=1;}
    
    void append(int x,int v) {
        int p=lstp,np=++cnt;lstp=np;ml[np]=ml[p]+1;vis[np]=1;pos[np]=v;
        for(;p&&tr[p][x]==0;p=par[p]) tr[p][x]=np;
        if(!p) return par[np]=qs,void();
        int q=tr[p][x];
        if(ml[p]+1<ml[q]) {
            int nq=++cnt;ml[nq]=ml[p]+1;pos[nq]=pos[q];
            memcpy(tr[nq],tr[q],sizeof tr[nq]);
            par[nq]=par[q],par[q]=par[np]=nq;
            for(;p&&tr[p][x]==q;p=par[p]) tr[p][x]=nq;
        } else par[np]=q;
    }

    void prepare() {
        for(int i=1;i<=cnt;i++) t[ml[i]]++;
        for(int i=1;i<=n;i++) t[i]+=t[i-1];
        for(int i=1;i<=cnt;i++) r[t[ml[i]]--]=i;

        for(int i=cnt,v;i;i--) if(vis[v=r[i]]) SGT.modify(rt[v],1,n,ml[v]);
        for(int i=cnt,v;i;i--) if(par[v=r[i]]) rt[par[v]]=SGT.merge(rt[par[v]],rt[v]);
    }

    void solve() {
        scanf("%s",s+1);
        int k=strlen(s+1),now=qs,rr=0,ans=0,x;
        for(int i=1,v;i<=k;i++)
            if(tr[now][v=s[i]-'0']) now=tr[now][v];
            else {rr=n+1;break;}
        if(!rr) rr=pos[now]-k+1,ans=k;now=qs;
        for(int i=1,v;i<=k;i++) {
            if(tr[now][v=s[i]-'0']) now=tr[now][v];
            else break;
            ans+=x=SGT.query(rt[now],1,n,1,min(rr+i-2,n));
        }ans+=rr-1;write(ans);
    }
}SAM;

int main() {
    read(n);
    scanf("%s",s+1);SAM.clear();
    for(int i=1;i<=n;i++) SAM.append(s[i]-'0',i);
    SAM.prepare();
    read(m);while(m--) SAM.solve();
    return 0;
}

[BZOJ3413]匹配

原文：https://www.cnblogs.com/hbyer/p/10471603.html