题解 P6727 [COCI2015-2016#5] OOP

· · 题解

提供一个线性的屑，跑的比 \operatorname{log} 慢一万倍！！!!11！1

一个询问串 A*B （长为 len）的限制有如下三条：(其中 A 表示 * 前面的子串，B 表示后面的）

  1. 前缀有 A
  2. 后缀有 B
  3. 长度 \ge len-1

只有满足这三点的串才会对这个询问产生 1 的贡献。如何维护？

先考虑前缀的限制，可以将所有模式串按照字典序排序，这样子的话，前缀为 A 的所有串都会在一个区间内。（具体实现为，加入到 trie 中然后 dfs 一遍 trie）

有了这个性质，一个询问就变成了：查询 [l,r] 中后缀有 B 且长度 \ge len 的串有多少个。

显然可以差分喵。也就是令 f(i,str,len) 表示 [1,i] 中后缀有 str 且长度 \ge len 的串的个数，答案即为 f(r,str,len)-f(l-1,str,len)。

然后离线，在排序后的模式串中，从 1 到 n 依次在 trie 加入每个串的反串，然后查询 f(i,str,len) 就是找到 str 的反串所对应 trie 上节点的子树内，有多少长度 \ge len 的串。

维护一个哈希表 h_{x,i} 表示 trie 树上的 x 节点的子树内，长度为 i 的串的个数。查询时，用子树内总串数减去长度 <len 的串数，得到合法数量。前者容易维护，后者就暴力扫一遍 h_{x,1} 到 h_{x,len-1} 求和。因为 len 和询问串长度同级，所以复杂度是 O(\text{总串长})。

这样就做到，线性解决询问了喵。

空间可能会有点点卡 QwQ

#include<bits/stdc++.h>
#define rgi register int
#define pbk push_back
#define pii pair<int,int>
#define fi first
#define se second 
#define fin(x) freopen(x,"r",stdin)
#define cl(x) memset(x,0,sizeof x)
using namespace std;
typedef long long ll;
const int N=100010,S=3000010,mod=4127021;
int n,m,l[S],r[S],T=1,ch[S][26],p[N],C,id[N],ans[N],d;
string s[N],t,g;
vector<int>b[S];
struct Hash{
    int h[mod+10],vx[S],vy[S],p[S],nxt[S],sz;
    inline void ins(int x,int y){
        for(rgi k=h[((ll)(x-1)*S+y-1)%mod];k;k=nxt[k])if(vx[k]==x&&vy[k]==y)return void(++p[k]);
        int pos=((ll)(x-1)*S+y-1)%mod;
        vx[++sz]=x,vy[sz]=y,p[sz]=1,nxt[sz]=h[pos],h[pos]=sz;
    }
    inline int ask(int x,int y){
        for(rgi k=h[((ll)(x-1)*S+y-1)%mod];k;k=nxt[k])if(vx[k]==x&&vy[k]==y)return p[k];
        return 0;
    }
}mp;
int F(int& x){return x?x:x=++T;}
int find(string s,int id=0,int h=0){
    int rt=1;
    for(char k:s){
        rt=F(ch[rt][k-'a']);
        if(h)mp.ins(rt,h),++l[rt];
    }
    if(id)b[rt].pbk(id);
    if(h)mp.ins(1,h),++l[1];
    return rt;
}
void dfs(int x){
    l[x]=C;
    for(rgi k:b[x])id[k]=++C;
    for(rgi to:ch[x])if(to)dfs(to);
    r[x]=C;
}
struct qry{
    int id,v,len;string s;
    void sol(){
        int G=l[d=find(s)];
        for(rgi i=1;i<len;++i)G-=mp.ask(d,i);
        ans[id]+=G*v;
    }
};
vector<qry>q[N];
signed main(){
    cin>>n>>m;
    for(rgi i=1;i<=n;++i)cin>>s[i],find(s[i],i);
    dfs(1);
    for(rgi i=1;i<=n;++i)p[id[i]]=i;
    for(rgi i=1,pos,k,L;i<=m;++i){
        cin>>t,L=t.size()-1,k=find(t.substr(0,pos=t.find('*')));
        g=t.substr(pos+1),reverse(g.begin(),g.end());
        q[r[k]].pbk(qry{i,1,L,g}),q[l[k]].pbk(qry{i,-1,L,g});
    }
    cl(ch),cl(l);
    for(rgi i=T=1;i<=n;++i){
        g=s[p[i]],reverse(g.begin(),g.end()),find(g,0,g.size());
        for(qry k:q[i])k.sol();
    }
    for(rgi i=1;i<=m;++i)cout<<ans[i]<<'\n';
    return 0;
}