SAM – OceanEye's Blog

Date Time

17/07/5 10:15

Author

后缀自动机+LCT
还没加LCT…… 现在是妥妥的TLE
等下再补LCT上去吧

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <map>

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

using namespace std;

namespace SAM
{
	int pcnt,last;
#define NIL 0
#define root 1
#define N 600010
	struct node
	{
//		map<int,int> ch;
		int ch[26];
		int fa,len,cnt;
//		init() { ch.clear();c fa=len,cnt=0; }
		node init() { memset(ch,0,sizeof(ch)); fa=len=cnt=0; }
//		int operator [] (const int &x) { if(ch.find(x)) return ch[x]; return 0; }
		int operator [] (const int &x) { return ch[x]; }
	}pool[N<<1];
	void dododo(int x)
	{ for(;x!=root;x=pool[x].fa) pool[x].cnt++; }
	void insert(int x)
	{
		static int node,p,q,nq;
		node=++pcnt; p=last; last=node;
		pool[node].len=pool[p].len+1;
		for(;!pool[p][x]&&p;p=pool[p].fa) pool[p].ch[x]=node;
		if(!p) { pool[node].fa=root; dododo(node); return; }
		q=pool[p][x];
		if(pool[q].len==pool[p].len+1) pool[node].fa=q;
		else
		{
			nq=++pcnt; pool[nq]=pool[q]; pool[nq].len=pool[p].len+1;
			pool[q].fa=pool[node].fa=nq;
			for(;p&&pool[p][x]==q;p=pool[p].fa)pool[p].ch[x]=nq;
		}
		dododo(node);
	}
	void insert(string x) { for(unsigned int i=0;i<x.length();i++) insert(x[i]-'A'); }
	int solve(string x)
	{
		static int node;
		node=root;
		for(unsigned int i=0;i<x.length();i++)
		{
			x[i]-='A';
			if(!pool[node][x[i]]) return 0;
			node=pool[node][x[i]];
		}
		return pool[node].cnt;
	}
	void init()
	{
		pcnt=last=1;
		pool[1].init();
	}
#undef N
#undef NIL
#undef root
}

string decode(string s,int mask)
{
	for(unsigned int j=0;j<s.length();j++)
	{
		mask=(mask*131+j) % s.length();
		char t=s[j];
		s[j]=s[mask];
		s[mask]=t;
	}
	return s;
}

int main()
{
	SAM::init();
	string s,ss;
	char cmd[10];
	int mask=0,m,ans;
	read(m); cin>>s; SAM::insert(s);
	for(;m;m--)
	{
		scanf("%s",cmd); cin>>s;
		ss=decode(s,mask);
		if(cmd[0]=='Q')
		{
			ans=SAM::solve(ss);
			mask^=ans;
			printf("%d\n",ans);
		}
		else SAM::insert(ss);
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <string>

#include <map>

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

char cc; int C;

template <class T>

void read( T &x )

{

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

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

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

x*=C;

}

using namespace std;

namespace SAM

{

int pcnt,last;

#define NIL 0

#define root 1

#define N 600010

struct node

{

// map<int,int> ch;

int ch[26];

int fa,len,cnt;

// init() { ch.clear();c fa=len,cnt=0; }

node init() { memset(ch,0,sizeof(ch)); fa=len=cnt=0; }

// int operator [] (const int &x) { if(ch.find(x)) return ch[x]; return 0; }

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

}pool[N<<1];

void dododo(int x)

{ for(;x!=root;x=pool[x].fa) pool[x].cnt++; }

void insert(int x)

{

static int node,p,q,nq;

node=++pcnt; p=last; last=node;

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

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

if(!p) { pool[node].fa=root; dododo(node); return; }

q=pool[p][x];

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

else

{

nq=++pcnt; pool[nq]=pool[q]; pool[nq].len=pool[p].len+1;

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

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

}

dododo(node);

}

void insert(string x) { for(unsigned int i=0;i<x.length();i++) insert(x[i]-'A'); }

int solve(string x)

{

static int node;

node=root;

for(unsigned int i=0;i<x.length();i++)

{

x[i]-='A';

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

node=pool[node][x[i]];

}

return pool[node].cnt;

}

void init()

{

pcnt=last=1;

pool[1].init();

}

#undef N

#undef NIL

#undef root

}

string decode(string s,int mask)

{

for(unsigned int j=0;j<s.length();j++)

{

mask=(mask*131+j) % s.length();

char t=s[j];

s[j]=s[mask];

s[mask]=t;

}

return s;

}

int main()

{

SAM::init();

string s,ss;

char cmd[10];

int mask=0,m,ans;

read(m); cin>>s; SAM::insert(s);

for(;m;m--)

{

scanf("%s",cmd); cin>>s;

ss=decode(s,mask);

if(cmd[0]=='Q')

{

ans=SAM::solve(ss);

mask^=ans;

printf("%d\n",ans);

}

else SAM::insert(ss);

}

Date Time

17/05/6 13:45

Author

OceanEye

广义后缀自动机

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

其实就是加完一个串之后把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

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

Date Time

Author

Category

Tags

BZOJ2555

Date Time

Author

Category

Tags

BZOJ2780