BZOJ 3277: 串（广义后缀自动机+DSU on Tree+倍增）

Posted On 2019年1月2日

3277: 串

先建广义后缀自动机，建时标记一下节点对应原位置，再跑一遍DSU On Tree得出每个结点表示的字符串在多少串中出现过，最后对于每次询问再跑一遍SAM，每次倍增找到当前点cur在Parent树上的祖先中（包含自己）满足条件的最深点tmp，该最深点tmp的len即为以当前位置i为结尾的后缀的答案

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=1e5*5+100;
struct sam{int len,fa,trans[27];}st[maxn];
struct zmc{int too,nxt;}e[maxn<<1];
int tott=1,now=1,root=1,tot,heavy[maxn],siz[maxn],last[maxn],cnt,bel[maxn],aw[maxn],f[maxn][20];
int sum[maxn],AW;
char s[maxn],total[maxn];
int beg[maxn];
inline int max(const int a,const int b){return a>b?a:b;}
inline int min(const int a,const int b){return a<b?a:b;}
void ins(const int pos,const int delta)
{
	if (delta==1)
	{
		if (!sum[pos])sum[pos]=1,++AW;
	}
	else AW=0,sum[pos]=0;
}
inline void extend(const int ch,const int col)
{
	int np=++tott,p=now;
	bel[np]=col;
	st[np].len=st[p].len+1;now=np;
	while (p&&!st[p].trans[ch])st[p].trans[ch]=np,p=st[p].fa;
	if (!p)st[np].fa=root;
	else
	{
		int q=st[p].trans[ch];
		if (st[p].len+1==st[q].len)st[np].fa=q;
		else
		{
			int nq=++tott;
			bel[nq]=col;
			st[nq]=st[q];
			st[nq].len=st[p].len+1;
			st[np].fa=st[q].fa=nq;
			while (p&&st[p].trans[ch]==q)st[p].trans[ch]=nq,p=st[p].fa;
		}
	}
}
inline void add(const int a,const int b)
{
	e[++cnt]=(zmc){b,last[a]};last[a]=cnt;
}
void dfs(const int cur)
{
	for (int i=1;i<=19;i++)
		f[cur][i]=f[f[cur][i-1]][i-1];
	siz[cur]=1;
	for (int i=last[cur];i;i=e[i].nxt)
		f[e[i].too][0]=cur,dfs(e[i].too),siz[cur]+=siz[e[i].too],siz[e[i].too]>siz[heavy[cur]]&&(heavy[cur]=e[i].too);
}
void cal(const int cur,const int delta)
{
	ins(bel[cur],delta);
	for (int i=last[cur];i;i=e[i].nxt)cal(e[i].too,delta);
}
void dsu(const int cur,const bool h)
{
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=heavy[cur])dsu(e[i].too,0);
	if (heavy[cur])dsu(heavy[cur],1);
	ins(bel[cur],1);
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=heavy[cur])cal(e[i].too,1);
	aw[cur]=AW;
	if (!h)cal(cur,-1);
}
int LEN[maxn];
int main()
{
	int n=read(),k=read(),ct=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		now=root;
		int len=strlen(s+1);
		LEN[i]=len;
		beg[i]=ct+1;
		for (int j=1;j<=len;j++)total[j+ct]=s[j];
		ct+=len+1;
		for (int j=1;j<=len;j++)extend(s[j]-'a',i);
	}
	for (int i=2;i<=tott;i++)add(st[i].fa,i);
	dfs(1);
	dsu(1,1);
	for (int i=1;i<=n;i++)
	{
		int cur=root,ans=0;
		for (int j=beg[i];j<beg[i]+LEN[i];j++)
		{
			int ch=total[j]-'a';
			if (st[cur].trans[ch])
			{
				cur=st[cur].trans[ch];int delta=st[cur].len;
				if (aw[cur]>=k)ans+=st[cur].len;
				else
				{
					for (int i=19;~i;i--)
						if (aw[f[cur][i]]<k&&f[cur][i])cur=f[cur][i];
					if (cur!=root)
					{
						cur=f[cur][0];
						if (aw[cur]>=k)
							ans+=min(st[cur].len,delta);
					}
				}
			}
		}
		printf("%d",ans);if (i!=n)putchar(' ');
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=1e5*5+100;

struct sam{int len,fa,trans[27];}st[maxn];

struct zmc{int too,nxt;}e[maxn<<1];

int tott=1,now=1,root=1,tot,heavy[maxn],siz[maxn],last[maxn],cnt,bel[maxn],aw[maxn],f[maxn][20];

int sum[maxn],AW;

char s[maxn],total[maxn];

int beg[maxn];

inline int max(const int a,const int b){return a>b?a:b;}

inline int min(const int a,const int b){return a<b?a:b;}

void ins(const int pos,const int delta)

{

if (delta==1)

{

if (!sum[pos])sum[pos]=1,++AW;

}

else AW=0,sum[pos]=0;

}

inline void extend(const int ch,const int col)

{

int np=++tott,p=now;

bel[np]=col;

st[np].len=st[p].len+1;now=np;

while (p&&!st[p].trans[ch])st[p].trans[ch]=np,p=st[p].fa;

if (!p)st[np].fa=root;

else

{

int q=st[p].trans[ch];

if (st[p].len+1==st[q].len)st[np].fa=q;

else

{

int nq=++tott;

bel[nq]=col;

st[nq]=st[q];

st[nq].len=st[p].len+1;

st[np].fa=st[q].fa=nq;

while (p&&st[p].trans[ch]==q)st[p].trans[ch]=nq,p=st[p].fa;

}

inline void add(const int a,const int b)

{

e[++cnt]=(zmc){b,last[a]};last[a]=cnt;

}

void dfs(const int cur)

{

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

f[cur][i]=f[f[cur][i-1]][i-1];

siz[cur]=1;

for (int i=last[cur];i;i=e[i].nxt)

f[e[i].too][0]=cur,dfs(e[i].too),siz[cur]+=siz[e[i].too],siz[e[i].too]>siz[heavy[cur]]&&(heavy[cur]=e[i].too);

}

void cal(const int cur,const int delta)

{

ins(bel[cur],delta);

for (int i=last[cur];i;i=e[i].nxt)cal(e[i].too,delta);

}

void dsu(const int cur,const bool h)

{

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=heavy[cur])dsu(e[i].too,0);

if (heavy[cur])dsu(heavy[cur],1);

ins(bel[cur],1);

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=heavy[cur])cal(e[i].too,1);

aw[cur]=AW;

if (!h)cal(cur,-1);

}

int LEN[maxn];

int main()

{

int n=read(),k=read(),ct=0;

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

{

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

now=root;

int len=strlen(s+1);

LEN[i]=len;

beg[i]=ct+1;

for (int j=1;j<=len;j++)total[j+ct]=s[j];

ct+=len+1;

for (int j=1;j<=len;j++)extend(s[j]-'a',i);

}

for (int i=2;i<=tott;i++)add(st[i].fa,i);

dfs(1);

dsu(1,1);

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

{

int cur=root,ans=0;

for (int j=beg[i];j<beg[i]+LEN[i];j++)

{

int ch=total[j]-'a';

if (st[cur].trans[ch])

{

cur=st[cur].trans[ch];int delta=st[cur].len;

if (aw[cur]>=k)ans+=st[cur].len;

else

{

for (int i=19;~i;i--)

if (aw[f[cur][i]]<k&&f[cur][i])cur=f[cur][i];

if (cur!=root)

{

cur=f[cur][0];

if (aw[cur]>=k)

ans+=min(st[cur].len,delta);

}

printf("%d",ans);if (i!=n)putchar(' ');

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments