1 条题解

  • 0
    @ 2025-10-19 16:46:55

    题解

    思路概述

    • 设母串为若干 s_{a_i} 的拼接。查询数量与字符串总长度均达 5e4，不能显式拼接。代码采取“短模式 / 长模式分治”的思路：
      1. 建立 AC 自动机（Solver1），把所有查询串插入；再逐段扫描 s_{a_i}，统计所有长度较短（≤ B）的查询次数。对于相邻块之间的跨界部分，利用预处理的后缀滚动匹配累加答案。
      2. 对长度较长的查询，使用后缀数组和 LCP 信息支撑：拼接所有 s_i 与查询串构建一个全局 SuffixArray，每个 s_i 预处理其在 SA 上的区间。随后通过“在线维护当前块的后缀 / 前缀”以及树状数组的统计，计算跨越多个字符串的出现次数。
    • 两部分结果叠加，就是每个查询的总出现次数。

    关键实现

    • Solver1 中的 nxt, fail, sum1/ sum2 对应 AC 自动机；对每个 s_i 顺序扫描、对子串跨越 B 的情况额外处理。
    • SuffixArray 封装了 build 与 RMQ 功能，node 结构存储一段在 SA 中的区间；通过合并不同块的 SA 区间来统计长串。
    • 复杂度近似 O((|S|+|queries|) log |S|)，其中 |S| 是所有字符串长度之和。

    注意事项

    • 大常数算法实现非常长，但思路核心是“短串 AC + 长串后缀数组”。最终把每次查询的累计次数输出即可。
    #include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 1000000009
#define ld long double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,val)memset(x,val,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,u)for(register int i=first[u],v=e[i].to;i;v=e[i=e[i].nxt].to)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,u)for(register i64 i=first[u];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
//#define D(i,j,n)for(int i=j;i>=n;i--)
//#define E(i,u)for(int i=first[u];i;i=e[i].nxt)
//#define F(i,j,n)for(int i=j;i<=n;i++)
//#define DL(i,j,n)for(register ll i=j;i>=n;i--)
//#define EL(i,u)for(register ll i=first[u];i;i=e[i].nxt)
//#define FL(i,j,n)for(register ll i=j;i<=n;i++)
ll read(){
	ll Ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')Ans=Ans*10+c-'0',c=getchar();
	return Ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1.5e5+5;
const int B = 1e3;
#define str vector<bool>
#define in(i,V) F(i,0,(i64)V.size()-1)
i64 n,m,q,a[maxn];char in[maxn];
str getstr(){
	scanf("%s",in+1);i64 L=strlen(in+1);
	str nw;F(i,1,L)nw.push_back(in[i]-'a');return nw;
}

str s[maxn],qr[maxn];i64 Ans[maxn];
namespace Solver1{
	i64 nxt[maxn][2],cnt[maxn],id[maxn],tot;

	i64 bel[maxn],dep[maxn];
	i64 ins(str V,i64 o=0){
		i64 now=0;bel[0]=o;
		in(i,V){
			if(!nxt[now][V[i]])
				dep[nxt[now][V[i]]=++tot]=i+1,bel[tot]=o;
			now=nxt[now][V[i]];
		}
		return now;
	}
	i64 fail[maxn];vector<i64>G[maxn];
	IV Build(){
		queue<i64>qwq;
		F(i,0,1)if(nxt[0][i])qwq.push(nxt[0][i]);
		while(!qwq.empty()){
			i64 u=qwq.front();qwq.pop();
			F(i,0,1)if(!nxt[u][i])nxt[u][i]=nxt[fail[u]][i];
			else qwq.push(nxt[u][i]),fail[nxt[u][i]]=nxt[fail[u]][i];
		}
		F(i,1,tot)G[fail[i]].push_back(i);
	}
	i64 sum1[maxn],sum2[maxn],ed[maxn];
	pair<i64,i64>Qr(i64 p){return{bel[ed[p]],dep[ed[p]]};}
	IV dfs(i64 u){
		for(i64 v:G[u]){
			dfs(v);
			sum1[u]+=sum1[v];
			sum2[u]+=sum2[v];
		}
	}
	IV solve(){
		F(i,1,m)cnt[a[i]]++;
		F(i,1,q)id[i]=ins(qr[i],i);Build();
		F(i,1,n){
			i64 now=0;
			for(auto x:s[i])
				now=nxt[now][x],sum1[now]+=cnt[i];
			ed[i]=now;
		}
		F(i,1,m){
			i64 cc=0,n1=ed[a[i]],n2=0;
			F(j,i+1,m){
				for(auto x:s[a[j]])
					if(++cc>B)break;
					else{
						n1=nxt[n1][x];n2=nxt[n2][x];
						sum2[n1]++;sum2[n2]--;
					}
				if(cc>B)break;
			}
		}
		dfs(0);
		F(i,1,q){
			Ans[i]=sum1[id[i]];
			if(qr[i].size()<=B)Ans[i]+=sum2[id[i]];
		}
	}
} // namespace Solver1

i64 sa[maxn];
struct SA{
	i64 n,s[maxn];i64 Push(i64 z){return s[++n]=z,n;}
	i64 h[maxn],rnk[maxn],w[maxn],tmp[maxn],in[maxn],out[maxn],mat[255];
	i64 st[maxn][22];
	i64 LCP(i64 l,i64 r){
		if(l==r)return n-l+1;if((l=rnk[l])>(r=rnk[r]))swap(l,r);
		i64 k=__lg(r-l++);return min(st[l][k],st[r-(1<<k)+1][k]);
	}
	IV geth(){
		i64 lst=0;
		F(i,1,n){
			lst=max(lst-1,0ll);if(rnk[i]==1)continue;
			while(s[sa[rnk[i]-1]+lst]==s[i+lst])lst++;
			h[rnk[i]]=lst;
		}
		// F(i,2,n)cout<<h[i]<<' ';puts("");
		F(i,1,n)st[i][0]=h[i];
		F(j,1,20)F(i,1,n-(1<<j)+1)
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
	IV Build(){
		F(i,1,n)mat[s[i]]=i;
		// F(i,1,n)cout<<s[i]<<' ';puts("");
		F(i,1,n)rnk[i]=s[i];
		auto Sort=[&](){
			static i64 cnt[maxn];

			i64 L=max(200ll,n);
			F(i,0,L)cnt[i]=0;
			F(i,1,n)cnt[w[i]]++;
			F(i,1,L)cnt[i]+=cnt[i-1];
			D(i,n,1)out[cnt[w[i]]--]=in[i];			
		};
		for(int k=1;k<=n;k<<=1){
			#define getk(x) (x+k>n?0:rnk[x+k])

			F(i,1,n)w[i]=getk(i),in[i]=i;Sort();
			// F(i,1,n)cout<<rnk[i]<<' ';puts("");
			F(i,1,n)w[i]=rnk[out[i]],in[i]=out[i];Sort();

			i64 cnt=0;
			// F(i,1,n)cout<<out[i]<<' ';puts("");
			F(i,1,n){
				if(i==1||rnk[out[i]]!=rnk[out[i-1]]||getk(out[i])!=getk(out[i-1]))
					cnt++;
				tmp[out[i]]=cnt;
			}
			F(i,1,n)rnk[i]=tmp[i];
			// F(i,1,n)cout<<rnk[i]<<' ';puts("");
			// puts("");
		}
		// F(i,1,n)cout<<rnk[i]<<' ';puts("");
		F(i,1,n)sa[rnk[i]]=i;
		// F(i,1,n)cout<<sa[i]<<' ';puts("");
		geth();
	}
}S;
struct node{
	i64 l,r;
	i64 len()const{return r-l+1;}
	IV print(){cout<<l<<' '<<r<<endl;}
};
i64 LCP(node A,node B){return min({S.LCP(A.l,B.l),A.len(),B.len()});}
bool cmp(node A,node B){
	i64 x=LCP(A,B);
	if(A.len()!=x&&B.len()!=x)
		return S.s[A.l+x]<S.s[B.l+x];
	return A.len()==x&&B.len()!=x;
}
i64 LCP(node A,node B,node C){
	i64 x=LCP(A,C);
	if(x<A.len()||x==C.len())return x;
	C.l+=x;return x+LCP(B,C);
}
bool ck(node A,node B,node C){
	//A+B<=C
	i64 x=LCP(A,B,C),v1=0,v2=0;
	if(x==C.len())v2=0;else v2=S.s[C.l+x];
	if(x<A.len())v1=S.s[A.l+x];
	else if(x<A.len()+B.len())v1=S.s[B.l+x-A.len()];
	return v1<=v2;
}
// node suf(i64 x){return node{x,S.n};}
node operator+(const node&A,const node&B){
	i64 L=0,mx=0;
	// cout<<sa[1]<<endl;
	D(i,20,0){
		i64 p=L+(1<<i);if(p>S.n)continue;
		if(!ck(A,B,node{sa[p],S.n}))L=p;
	}
	node Ans=A;mx=A.len();
	// cout<<sa[L]<<' '<<sa[L+1]<<endl;
	// cout<<"?"<<L<<endl;
	auto upd=[&](i64 L){
		// cout<<sa[L]<<endl;
		i64 t=LCP(A,B,node{sa[L],S.n});
		// cout<<sa[L]<<endl;
		// cout<<t<<endl;
		if(mx<t)mx=t,Ans=node{sa[L],sa[L]+t-1};
	};
	if(L)upd(L);if(L<S.n)upd(L+1);return Ans;
}
i64 pos[maxn];node wi[maxn],pre[maxn],suf[maxn];

struct KMP{
	vector<i64>G[maxn];
	i64 Bd[maxn],w[maxn],n,f[maxn][22],dfn[maxn],low[maxn],dft;
	IV dfs(i64 u){dfn[u]=++dft;for(i64 v:G[u])dfs(v);low[u]=dft;}
	IV Build(){
		Bd[1]=0;i64 now=0;dft=0;
		F(i,0,n)G[i].clear();
		F(i,2,n){
			while(now&&w[now+1]!=w[i])now=Bd[now];
			if(w[now+1]==w[i])now++;Bd[i]=now;
		}
		F(i,1,n)G[f[i][0]=Bd[i]].push_back(i);
		F(j,1,20)F(i,1,n)f[i][j]=f[f[i][j-1]][j-1];dfs(0);
	}
	i64 loc(i64 o,i64 L){
		if(o<=L)return o;
		D(i,20,0)if(f[o][i]>L)o=f[o][i];
		return f[o][0];
	}
	IV Trs(i64&x,i64 p){
		while(x&&(x==n||w[x+1]!=p))x=Bd[x];
		if(w[x+1]==p)x++;
	}
}pr,sf;
struct BIT{
	i64 c[maxn],ans,n;
	IV init(i64 N){mem(c,0);n=N;F(i,1,n)c[i]=0;}
	IV add(i64 p,i64 v){for(;p<=n;p+=p&-p)c[p]+=v;}
	IV add(i64 l,i64 r,i64 v){
		// cout<<"add"<<l<<' '<<r<<' '<<v<<endl;
		add(l,v);add(r+1,-v);
	}
	i64 Q(i64 p){ans=0;for(;p;p-=p&-p)ans+=c[p];return ans;}
}bit;
vector<i64>qwq[maxn];i64 Tmp,C;
IV dfs(i64 u){
	// cerr<<u<<endl;
	if(u&&u!=C)bit.add(sf.dfn[C-u],sf.low[C-u],1);

	for(i64 v:qwq[u])Tmp+=bit.Q(sf.dfn[v]);
	for(i64 v:pr.G[u])dfs(v);

	if(u&&u!=C)bit.add(sf.dfn[C-u],sf.low[C-u],-1);
}
i64 pL[maxn],sL[maxn];
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);

	n=read();m=read();q=read();
	F(i,1,n)s[i]=getstr();
	F(i,1,m)a[i]=read();
	F(i,1,q)qr[i]=getstr();
	Solver1::solve();
	F(i,1,q){
		pos[i]=S.n+1;
		for(auto x:qr[i])S.Push(x);S.Push(2);
	}
	S.Build();
	// cout<<LCP(node{2,2},node{3,3},node{2,4})<<endl;
	// (node{4,4}+node{4,4}).print();
	// exit(0);
	F(i,1,n){
		reverse(s[i].begin(),s[i].end());
		for(auto x:s[i]){
			i64 z=S.mat[x];
			// cout<<x<<' '<<z<<endl;
			if(!z){wi[i]={1,0};continue;}
			wi[i]=node{z,z}+wi[i];
		}
		// wi[i].print();
		reverse(s[i].begin(),s[i].end());
	}
	suf[m+1]={1,0};
	D(i,m,1){
		// wi[a[i]].print();
		if(wi[a[i]].len()==s[a[i]].size())
			suf[i]=wi[a[i]]+suf[i+1];
		else suf[i]=wi[a[i]];
		auto[id,d]=Solver1::Qr(a[i]);
		pre[i]={pos[id],pos[id]+d-1};
	}
	//
	// F(i,1,m)pre[i].print();
	// puts("");
	// F(i,1,m)suf[i].print();
	// exit(0);

	F(o,1,q)if(qr[o].size()>B){
		C=(i64)qr[o].size();pr.n=sf.n=C;
		F(i,1,C)pr.w[i]=sf.w[C-i+1]=qr[o][i-1];
		pr.Build();sf.Build();

		i64 now=0;
		F(i,1,S.n)pr.Trs(now,S.s[i]),pL[i]=now;
		D(i,S.n,1)sf.Trs(now,S.s[i]),sL[i]=now;
		F(i,0,C)qwq[i].clear();Tmp=0;
		bit.init(C+1);
		// cout<<C<<endl;
		F(i,1,m-1){
			i64 x=pr.loc(pL[pre[i].r],pre[i].len());
			i64 y=sf.loc(sL[suf[i+1].l],suf[i+1].len());
			// pre[i].print();
			// cout<<pre[i].len()<<' '<<suf[i+1].len()<<endl;
			// cout<<pL[pre[i].r]<<' '<<x<<' '<<y<<endl;
			// cout<<x<<' '<<y<<endl;
			if(x+y<C)continue;
			qwq[x].push_back(y);
		}
		dfs(0);
		Ans[o]+=Tmp;
	}
	
	F(i,1,q)printf("%lld\n",Ans[i]);
	return 0;
}
    • 1

    「2018 集训队互测 Day 5」Fim4

    信息

    ID
    3405
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    1
    已通过
    1
    上传者
    1. 评测队列
    2. 服务状态
    3. 兼容模式
    4. 主题
    2. 黔ICP备2023002402号-2
    3. Worker 0, 66ms
    4. Powered by Hydro v4.19.1 Community, Modified by 33DAI