BZOJ2434

@OceanEye7年前

05/7

22:56

OceanEye 撰写 AC自动机 BZOJ DFS序树树状数组无回复

AC自动机的好题，充分利用了fail树的性质

性质：S串中每个包含了T的后缀的fail指针一定经过若干层指向T

fail指针不成环

把fail树上的点dfs重标号

处理单个询问时可以把S串中的每个节点的DFS序丢进树状数组里面

查询T对应节点的DFS区间即可

处理许多询问的话离线处理即可

为了保证在树上不跑 \(x^2\) 次

可以模拟之前插入节点的方式来计算……

当然开个vector在节点上记录id也是可行的……

代码应该很好看懂

[但是我写的代码一般都巨长所以没多少人看哈哈哈]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

#define N 100010
#define E 200010
#define BASE 'a'
#define root 0

#define lb(x) (x&-x)
int Arr[N];
void add(int pos)
{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }
void dec(int pos)
{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }
int query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
	return ret;
}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)
{
	TO[e_tot]=__;
	NXT[e_tot]=fst[_];
	fst[_]=e_tot++;
}

struct node
{
	int ch[26],fail;
	int fa;
	node() { for(int i=0;i<26;i++) ch[i]=-1; }
	vector <int> rec;
	int operator [] (const int &x) { return ch[x]; }
}pool[N];

int pcnt;
int tot,he[N],l[N],r[N],_____;

void dfs(int x)
{
	l[x]=++_____;
	for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);
	r[x]=_____;
}

void build()
{
	int x,node;
	queue <int> Q;
	Q.push(0);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		for(int i=0;i<26;i++)
		{
			if(!~pool[x][i]) continue;
			node=pool[x].fail;
			while(~node&&!~pool[node][i]) node=pool[node].fail;
			if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];
			else pool[pool[x][i]].fail=root;
			Q.push(pool[x][i]);
		}
	}
	for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);
}

char s[N];
int Len;

void pre()
{
	memset(fst,-1,sizeof(fst));
	int now=0;
	pool[0].fail=pool[0].fa=-1;
	scanf("%s",s);
	Len=strlen(s);
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			pool[now].rec.push_back(++tot);
			he[tot]=now;
			continue;
		}
		if(s[i]=='B')
		{
			now=pool[now].fa;
			continue;
		}
		s[i]-=BASE;
		if(!~pool[now][s[i]])
		{
			pool[now].ch[s[i]]=++pcnt;
			pool[pcnt].fa=now;
		}
		now=pool[now][s[i]];
	}
	build();
	dfs(0);
}
vector <int> q[N];
int m,node,ans[N],B;
int A[N];

void solve()
{
	int now=0,__=0;
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			__++;
			for(int k=0;k<q[__].size();k++)
				ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);
			continue;
		}
		if(s[i]=='B')
		{
			dec(l[now]);
			now=pool[now].fa;
			continue;
		}
		now=pool[now][s[i]];
		add(l[now]);
	}
}

int main()
{
//	freopen("BZOJ2434.in","r",stdin);
	pre();
	read(m);
	for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }
	solve();
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <vector>

#include <iostream>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define E 200010

#define BASE 'a'

#define root 0

#define lb(x) (x&-x)

int Arr[N];

void add(int pos)

{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }

void dec(int pos)

{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)

{

TO[e_tot]=__;

NXT[e_tot]=fst[_];

fst[_]=e_tot++;

}

struct node

{

int ch[26],fail;

int fa;

node() { for(int i=0;i<26;i++) ch[i]=-1; }

vector <int> rec;

int operator [] (const int &x) { return ch[x]; }

}pool[N];

int pcnt;

int tot,he[N],l[N],r[N],_____;

void dfs(int x)

{

l[x]=++_____;

for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);

r[x]=_____;

}

void build()

{

int x,node;

queue <int> Q;

Q.push(0);

while(!Q.empty())

{

x=Q.front(); Q.pop();

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

{

if(!~pool[x][i]) continue;

node=pool[x].fail;

while(~node&&!~pool[node][i]) node=pool[node].fail;

if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];

else pool[pool[x][i]].fail=root;

Q.push(pool[x][i]);

}

for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);

}

char s[N];

int Len;

void pre()

{

memset(fst,-1,sizeof(fst));

int now=0;

pool[0].fail=pool[0].fa=-1;

scanf("%s",s);

Len=strlen(s);

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

{

if(s[i]=='P')

{

pool[now].rec.push_back(++tot);

he[tot]=now;

continue;

}

if(s[i]=='B')

{

now=pool[now].fa;

continue;

}

s[i]-=BASE;

if(!~pool[now][s[i]])

{

pool[now].ch[s[i]]=++pcnt;

pool[pcnt].fa=now;

}

now=pool[now][s[i]];

}

build();

dfs(0);

}

vector <int> q[N];

int m,node,ans[N],B;

int A[N];

void solve()

{

int now=0,__=0;

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

{

if(s[i]=='P')

{

__++;

for(int k=0;k<q[__].size();k++)

ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);

continue;

}

if(s[i]=='B')

{

dec(l[now]);

now=pool[now].fa;

continue;

}

now=pool[now][s[i]];

add(l[now]);

}

int main()

{

// freopen("BZOJ2434.in","r",stdin);

pre();

read(m);

for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }

solve();

for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ2434

BZOJ2434

撤销评论

近期文章

标签