分析

首先考虑只有一个串时的做法，可以进行背包dp，记\(f(i,j)\)表示从\(i\)的子树中某点出发到\(i\)能否匹配字符串的\(1 \dots j\)位且\(i\)与\(j\)匹配。同时记\(g(i,j)\)表示从\(i\)出发到\(i\)的子树某点中能否匹配字符串的\(j \dots len\)位并且\(i\)与\(j\)匹配。

显然有

\[f(i,j)=f(i,j)|(f(k,j−1)\&[ch=s_j]),f(i,0)=true\\
g(i,j)=g(i,j)|(g(k,j+1)\&[ch=s_j]),g(i,len+1)=true
\]

(\(k\)为\(i\)的儿子,\(ch\)为当前边上的字符)

把询问串拼接在一起（中间留空以防出错），\(f\)与\(g\)的区间含义改成在当前点所属串的区间含义，在父亲处合并儿子的答案并对最终答案做出贡献。如果存在\(f(i,j)=true\)且\(g(i,j+1)=true\)那么\(j\)点所属串就可以在以\(i\)为子树的字符树中匹配。

用拓扑排序确定计算顺序避免递归爆栈，用bitset优化位运算的转移提高时空效率。最后注意bzoj太慢了，所以可以把长度为1的询问串特判掉来优化常数。

时空复杂度\(O(N \cdot ∑len / 64)\)。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x){

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=30010,MAXM=35010;

struct Edge

{

	int nx,to,w;

}E[MAXN<<1];

int head[MAXN],ecnt;

void addedge(int x,int y,int w)

{

	E[++ecnt].to=y,E[ecnt].w=w;

	E[ecnt].nx=head[x],head[x]=ecnt;

}

bool exist[27]; // character exist

int s[MAXM],t[MAXM]; // string starting and ending point

char st[MAXM]; // buffer

int ch[MAXM],bl[MAXM]; // new combined string,owner of position

bool final[MAXM]; // final answer,sorted by query rank

queue <int> Q;

void dfs(int x,int fa) // topu sort

{

	for(int i=head[x];i;i=E[i].nx)

		if(E[i].to!=fa)

			dfs(E[i].to,x);

	Q.push(x);

}

bool vis[MAXN]; // avoid accessing father

bitset<MAXM> pre,suf,f[MAXN],g[MAXN],hav[27],ans,nowpre,nowsuf;

void bfs()

{

	while(!Q.empty())

	{

		int x=Q.front();

		Q.pop();

		vis[x]=true;

		f[x]=pre,g[x]=suf;

		for(int i=head[x];i;i=E[i].nx)

		{

			int y=E[i].to,w=E[i].w;

			if(!vis[y]) continue;

			nowpre=(f[y]<<1)&hav[w];

			nowsuf=(g[y]>>1)&hav[w];

			ans=ans|(f[x]&(nowsuf>>1))|(nowpre&(g[x]>>1)); // 避免在同一条链上合并答案

			f[x]=f[x]|nowpre,g[x]=g[x]|nowsuf;

		}

	}

}

int main()

{

  freopen("4713.in","r",stdin);

  freopen("4713.out","w",stdout);

	int n;

	read(n);

	for(int i=1;i<n;++i)

	{

		int x,y;

		char w[2];

		read(x);read(y);

		scanf("%s",w);

		w[0]-='a'-1;

		addedge(x,y,w[0]);

		addedge(y,x,w[0]);

		exist[int(w[0])]=true;

	}

	int m;

	read(m);

	int sum=0;

	for(int i=1;i<=m;++i)

	{

		s[i]=sum; // 两两字符串之间留空以防错。字符串前一位置留空

		scanf("%s",st+1);

		int l=strlen(st+1);

		if(l==1)

		{

			if(exist[st[1]-'a'+1])

				final[i]=true;

			continue;

		}

		for(int j=1;j<=l;++j)

			ch[sum+j]=st[j]-'a'+1;

		t[i]=sum+l+1;

		for(int j=s[i];j<t[i];++j)

			bl[j]=i;

		sum=sum+l+1;

	}

	for(int i=1;i<=m;++i)

	{ // 给f,g初始化

		pre.set(s[i]);

		suf.set(t[i]);

	}

	for(int i=0;i<=sum;++i)

		hav[ch[i]].set(i); // f,g转移用

	dfs(1,0);

	bfs();

	for(int i=0;i<=sum;++i)

		if(ans[i])

			final[bl[i]]=true;

	for(int i=1;i<=m;++i)

		if(final[i])

			puts("YES");

		else

			puts("NO");

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

巴特西

BZOJ4713 迷失的字符串

分析

代码

最新文章

热门文章