自动搬运

查看原文

来自洛谷，原作者为

	Miko35 阿玮你又在打电动喔，去看会书好不好

搬运于2025-08-24 22:23:25，当前版本为作者最后更新于2021-09-14 20:21:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一个线性的屑，跑的比 $\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;
}