HDU 5069 Harry And Biological Teacher（AC自动机+线段树）

题意

给定 \(n\) 个字符串，\(m\) 个询问，每次询问 \(a\) 字符串的后缀和 \(b\) 字符串的前缀最多能匹配多长。

\(1\leq n,m \leq 10^5\)

思路

多串匹配，考虑 \(\text{AC}\)自动机，对 \(n\) 个串建自动机，观察这个结构，不难发现 \(Trie\) 树的结构和前缀有关，\(fail\) 树的结构和后缀有关。

考虑离线，对于每个 \(b\) ，存储它对应的 \(a\) ，我们通过在自动机上扫 \(b\) 来回答。由于扫到某节点 \(u\) ，在 \(fail\) 树上 \(u\) 的子节点都能得到 \(u\) 在 \(Trie\) 树上深度的贡献，最后对每一个 \(a\)，查询它在自动机位置上的贡献最大值即可。用线段树维护 \(fail\) 树的 \(\text{dfs}\) 序，区间修改最大值，单点查询最大值。

\(\text{AC}\)自动机上有 \(Trie,fail\) 两棵树，分别包含前后缀的信息，这类问题可以通过 \(\text{AC}\)自动机，转化为树上问题。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

#define x first

#define y second

typedef long long LL;

using namespace std;

typedef pair<int,int> pii;

const int N=1e5+5;

const int NN=N*22;

int c_d[256];

template<const int maxn,const int maxm>struct Linked_list

{

	int head[maxn],to[maxm],nxt[maxm],tot;

	Linked_list(){clear();}

	void clear(){memset(head,-1,sizeof(head));tot=0;}

	void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}

	#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])

};

struct SegmentTree

{

	int lson[NN],rson[NN],tag[NN];

	int rt,tot;

	void build()

	{

		tag[0]=lson[0]=rson[0]=0;

		rt=tot=0;

	}

	void create(int &k)

	{

		if(!k)

		{

			k=++tot;

			tag[k]=lson[k]=rson[k]=0;

		}

	}

	void update(int &k,int L,int R,int val,int l,int r)

	{

		create(k);

		if(L<=l&&r<=R){tag[k]=max(tag[k],val);return;}

		int mid=(l+r)>>1;

		if(L<=mid)update(lson[k],L,R,val,l,mid);

		if(R>mid)update(rson[k],L,R,val,mid+1,r);

	}

	int query(int k,int x,int l,int r)

	{

		if(l==r)return tag[k];

		int mid=(l+r)>>1;

		if(x<=mid)return max(query(lson[k],x,l,mid),tag[k]);

		else return max(query(rson[k],x,mid+1,r),tag[k]);

	}

}ST;

Linked_list<N,N>G;

int L[N],R[N],ord;

int ch[N][4],f[N],dep[N];

string P[N];

int rt,tot;

vector<pii>Qry[N];int Ans[N];

char str[N];

int idx[N];

int n,q;

void build(){rt=tot=0;}

void create(int &k)

{

	if(!k)

	{

		k=++tot;

		FOR(i,0,3)ch[k][i]=0;

	}

}

void insert(int &k,string &str,int id)

{

	create(k);

	int now=k;dep[now]=0;

	FOR(i,0,str.length()-1)

	{

		create(ch[now][c_d[(int)str[i]]]);

		now=ch[now][c_d[(int)str[i]]];

		dep[now]=i+1;

	}

	idx[id]=now;

}

void get_fail()

{

	queue<int>Q;

	while(!Q.empty())Q.pop();

	f[rt]=rt;

	FOR(i,0,3)

	{

		if(ch[rt][i])f[ch[rt][i]]=rt,Q.push(ch[rt][i]);

		else ch[rt][i]=rt;

	}

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		FOR(i,0,3)

		{

			if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],Q.push(ch[u][i]);

			else ch[u][i]=ch[f[u]][i];

		}

	}

}

void dfs_fail(int u)

{

	L[u]=++ord;

	EOR(i,G,u)dfs_fail(G.to[i]);

	R[u]=ord;

}

void query(int k,string &str,vector<pii>&vec)

{

	ST.build();

	int now=k;

	ST.update(ST.rt,L[now],R[now],dep[now],1,tot);

	FOR(i,0,str.length()-1)

	{

		now=ch[now][c_d[(int)str[i]]];

		ST.update(ST.rt,L[now],R[now],dep[now],1,tot);

	}

	FOR(i,0,(int)vec.size()-1)Ans[vec[i].y]=ST.query(ST.rt,vec[i].x,1,tot);

}

int main()

{

	c_d[(int)'A']=0,c_d[(int)'C']=1,c_d[(int)'G']=2,c_d[(int)'T']=3;

	while(~scanf("%d%d",&n,&q))

	{

		G.clear(),build();

		FOR(i,1,n)Qry[i].clear();

		FOR(i,1,n)

		{

			cin>>P[i];

			insert(rt,P[i],i);

		}

		get_fail();

		FOR(i,1,tot)if(f[i]!=i)G.add(f[i],i);

		ord=0;dfs_fail(rt);

		FOR(i,1,q)

		{

			int a,b;

			scanf("%d%d",&a,&b);

			Qry[b].push_back(pii(L[idx[a]],i));

		}

		FOR(i,1,n)query(rt,P[i],Qry[i]);

		FOR(i,1,q)printf("%d\n",Ans[i]);

	}

	return 0;

}

巴特西

HDU 5069 Harry And Biological Teacher（AC自动机+线段树）

题意

思路

代码

最新文章

热门文章