BZOJ2780

@OceanEye7年前

05/6

13:45

OceanEye 撰写 BZOJ SAM 无回复

广义后缀自动机

良心题，教会了我怎么写广义后缀自动机……

其实就是加完一个串之后把last丢回root接着跑啊qaq

这是非TRIE树版本

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

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

using namespace std;

#define SIZ 100010
#define N 10010

namespace SAM
{
#define lb(x) (x&-x)
	int Arr[SIZ<<1];
	void inc(int x,int val) { while(x<=(SIZ<<1)) Arr[x]+=val,x+=lb(x); }
	int query(int pos)
	{
		int ret=0;
		while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
		return ret;
	}
#undef lb
	struct node
	{
		int ch[26],fa;
		int len,cnt,col;
		int operator [] (const int &x) { return ch[x]; }
		node() { for(int i=0;i<26;i++) ch[i]=-1; }
	}pool[SIZ<<1];
	int pcnt,last,n,len;
	int C[SIZ<<1],que[SIZ<<1],ans[N];
#define root 0
#define NIL -1
#define BASE 'a'
	char ss[SIZ<<1];
	string s[N];
	bool inq[SIZ<<1];
	queue <int> Q;
	void build(int id)
	{
		last=0;
		int x,node,q,nq;
		char buf;
		len=strlen(ss);
		for(int i=0;i<len;i++)
		{
			buf=ss[i]; buf-=BASE;
			node=++pcnt; x=last;
			pool[node].len=pool[x].len+1;
			last=node;
			for(;~x&&!~pool[x][buf];x=pool[x].fa) pool[x].ch[buf]=node;
			if(!~x)
			{
				pool[node].fa=root;
				continue;
			}
			q=pool[x][buf];
			if(pool[x].len+1==pool[q].len) pool[node].fa=q;
			else
			{
				nq=++pcnt; pool[nq]=pool[q];
				pool[nq].len=pool[x].len+1;
				pool[q].fa=pool[node].fa=nq;
				for(;pool[x][buf]==q&&~x;x=pool[x].fa) pool[x].ch[buf]=nq;
			}
		}
	}
	void rebuild(int id)
	{
		int node=0,p;
		char buf;
		len=s[id].length();
		for(int i=0;i<len;i++)
		{
			buf=s[id][i];
			node=pool[node][buf-BASE];
			for(p=node;~p&&pool[p].col!=id;p=pool[p].fa)
			{
				pool[p].cnt++;
				pool[p].col=id;
			}
		}
	}
	void init(int _)
	{
		pool[root].fa=-1;
		pool[root].len=0;
		n=_;
		int x;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",ss);
			s[i]=string(ss);
			build(i);
		}
		for(int i=1;i<=n;i++)
			rebuild(i);
	}
	int solve(char a[])
	{
		int len=strlen(a);
		int node=0;
		for(int i=0;i<len;i++)
		{
			a[i]-=BASE;
			if(!~pool[node][a[i]])return 0;
			node=pool[node][a[i]];
		}
		return pool[node].cnt;
	}
}

int n,m;
char T[SIZ<<2];
int main()
{
	freopen("BZOJ2780.in","r",stdin);
	read(n); read(m);
	SAM::init(n);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",T);
		printf("%d\n",SAM::solve(T));
	}
//	SAM::solve(0);
//	SAM::out();
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <string>

#include <vector>

#include <queue>

#define ll long long

#define INF 1000000000

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

char cc; int X;

template <class T>

void read( T &x )

{

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

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

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

x*=X;

}

using namespace std;

#define SIZ 100010

#define N 10010

namespace SAM

{

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

int Arr[SIZ<<1];

void inc(int x,int val) { while(x<=(SIZ<<1)) Arr[x]+=val,x+=lb(x); }

int query(int pos)

{

int ret=0;

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

return ret;

}

#undef lb

struct node

{

int ch[26],fa;

int len,cnt,col;

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

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

}pool[SIZ<<1];

int pcnt,last,n,len;

int C[SIZ<<1],que[SIZ<<1],ans[N];

#define root 0

#define NIL -1

#define BASE 'a'

char ss[SIZ<<1];

string s[N];

bool inq[SIZ<<1];

queue <int> Q;

void build(int id)

{

last=0;

int x,node,q,nq;

char buf;

len=strlen(ss);

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

{

buf=ss[i]; buf-=BASE;

node=++pcnt; x=last;

pool[node].len=pool[x].len+1;

last=node;

for(;~x&&!~pool[x][buf];x=pool[x].fa) pool[x].ch[buf]=node;

if(!~x)

{

pool[node].fa=root;

continue;

}

q=pool[x][buf];

if(pool[x].len+1==pool[q].len) pool[node].fa=q;

else

{

nq=++pcnt; pool[nq]=pool[q];

pool[nq].len=pool[x].len+1;

pool[q].fa=pool[node].fa=nq;

for(;pool[x][buf]==q&&~x;x=pool[x].fa) pool[x].ch[buf]=nq;

}

void rebuild(int id)

{

int node=0,p;

char buf;

len=s[id].length();

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

{

buf=s[id][i];

node=pool[node][buf-BASE];

for(p=node;~p&&pool[p].col!=id;p=pool[p].fa)

{

pool[p].cnt++;

pool[p].col=id;

}

void init(int _)

{

pool[root].fa=-1;

pool[root].len=0;

n=_;

int x;

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

{

scanf("%s",ss);

s[i]=string(ss);

build(i);

}

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

rebuild(i);

}

int solve(char a[])

{

int len=strlen(a);

int node=0;

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

{

a[i]-=BASE;

if(!~pool[node][a[i]])return 0;

node=pool[node][a[i]];

}

return pool[node].cnt;

}

int n,m;

char T[SIZ<<2];

int main()

{

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

read(n); read(m);

SAM::init(n);

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

{

scanf("%s",T);

printf("%d\n",SAM::solve(T));

}

// SAM::solve(0);

// SAM::out();

return 0;

}

TRIE树什么的等会再写

OceanEye's Blog

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

@OceanEye7年前

BZOJ2780

BZOJ2780

撤销评论

近期文章

标签