Codeforces 666 E.Forensic Examination（伪广义后缀自动机+线段树合并）

Posted On 2019年1月2日

E. Forensic Examination

Translation

给定一个串S和若干个串Ti
每次询问S[pl..pr]在r-l+1个串T[l..r]中出现的最多次数（在每个Ti串中），以及出现次数最多的那个串的编号

Solution

将S串和各个T串建在同一个SAM中，并对于每个非nq结点打标记插入线段树中，中间用分隔符隔开

再把询问存到对应位置（在S串中的位置，可以倍增得到）的vector中，边线段树合并边统计答案

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
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=1.5e6+100;
struct sam{int len,fa,trans[27];}st[maxn<<1];
struct zmc{int too,nxt;}e[maxn<<1];
int curT;
struct seg{int lc,rc,mx;unsigned int mxpos;}t[(maxn<<3)];
int tott=1,now=1,root=1,tot,last[maxn],cnt,pool,rt[maxn],n,pos[maxn],f[maxn][21];
struct ask{int l,r,pos;};
vector<ask>store[maxn];
pair<int,int>ans[maxn];
char s[maxn],S[maxn];
inline int max(const int a,const int b)
{
	return a>b?a:b;
}
void ins(int&cur,const int l,const int r,const int pos)
{
	if (!cur)cur=++pool;
	if (l==r)return(void)(++t[cur].mx,t[cur].mxpos=l);
	int mid=(l+r)>>1;
	if (pos<=mid)ins(t[cur].lc,l,mid,pos);
	else ins(t[cur].rc,mid+1,r,pos);
	t[cur].mx=t[t[cur].lc].mx;
	t[cur].mxpos=t[t[cur].lc].mxpos;
	if (t[t[cur].rc].mx>t[cur].mx)
		t[cur].mx=t[t[cur].rc].mx,t[cur].mxpos=t[t[cur].rc].mxpos;;
}
int merge(int&x,const int y,const int l,const int r)
{
	if (!x||!y)return x|y;
	if (!x)x=++pool;
	t[x].mx+=t[y].mx;
	int mid=(l+r)>>1;
	t[x].lc=merge(t[x].lc,t[y].lc,l,mid);
	t[x].rc=merge(t[x].rc,t[y].rc,mid+1,r);
	if (l==r)t[x].mxpos=l;
	else
	{
		t[x].mx=t[t[x].lc].mx;
		t[x].mxpos=t[t[x].lc].mxpos;
		if (t[t[x].rc].mx>t[x].mx)
		{
			t[x].mx=t[t[x].rc].mx;
			t[x].mxpos=t[t[x].rc].mxpos;
		}
	}
	return x;
}
inline void extend(const int ch,const int col)
{
	int np=++tott,p=now;ins(rt[tott],1,n+1,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;
			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;
}
pair<int,int>query(const int cur,const int l,const int r,const int L,const int R)
{
	if (L<=l&&r<=R)return make_pair(t[cur].mx,-t[cur].mxpos);
	int mid=(l+r)>>1;
	pair<int,int>ans=make_pair(0,-1e9);
	if (L<=mid)ans=query(t[cur].lc,l,mid,L,R);
	if (R>mid)ans=max(ans,query(t[cur].rc,mid+1,r,L,R));
	return ans;
}
void dfs(const int cur)
{
	for (int i=last[cur];i;i=e[i].nxt)
		dfs(e[i].too),rt[cur]=merge(rt[cur],rt[e[i].too],1,n+1);
	for(vector<ask>::iterator it=store[cur].begin();it!=store[cur].end();++it)
	{
		ans[(*it).pos]=query(rt[cur],1,n+1,(*it).l,(*it).r);
		if (!ans[(*it).pos].first)ans[(*it).pos].second=-(*it).l;
	}
}
void predfs(const int cur)
{
	for (int i=1;i<=20;i++)f[cur][i]=f[f[cur][i-1]][i-1];
	for (int i=last[cur];i;i=e[i].nxt)
		f[e[i].too][0]=cur,predfs(e[i].too);
}
signed main()
{
	scanf("%s",s+1);
	int len=strlen(s+1);
	n=read();
	for (int i=1;i<=len;i++)extend(s[i]-'a',n+1);
	extend(26,n+1);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",S+1);
		int len=strlen(S+1);
		for (int j=1;j<=len;j++)extend(S[j]-'a',i);
		extend(26,i);
	}
	for (int i=1,cur=root;i<=len;i++)cur=st[cur].trans[s[i]-'a'],pos[i]=cur;
	for (int i=1;i<=tott;i++)add(st[i].fa,i);
	predfs(1);
	int m=read();
	for (int Pos=1;Pos<=m;Pos++)
	{
		int l=read(),r=read(),L=read(),R=read(),cur=pos[R];
		for (int i=20;~i;i--)
			if (st[f[cur][i]].len>=R-L+1)cur=f[cur][i];
		store[cur].push_back((ask){l,r,Pos});
	}
	dfs(1);
	for (int i=1;i<=m;i++)printf("%d %d\n",-ans[i].second,ans[i].first);
}

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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

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=1.5e6+100;

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

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

int curT;

struct seg{int lc,rc,mx;unsigned int mxpos;}t[(maxn<<3)];

int tott=1,now=1,root=1,tot,last[maxn],cnt,pool,rt[maxn],n,pos[maxn],f[maxn][21];

struct ask{int l,r,pos;};

vector<ask>store[maxn];

pair<int,int>ans[maxn];

char s[maxn],S[maxn];

inline int max(const int a,const int b)

{

return a>b?a:b;

}

void ins(int&cur,const int l,const int r,const int pos)

{

if (!cur)cur=++pool;

if (l==r)return(void)(++t[cur].mx,t[cur].mxpos=l);

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

if (pos<=mid)ins(t[cur].lc,l,mid,pos);

else ins(t[cur].rc,mid+1,r,pos);

t[cur].mx=t[t[cur].lc].mx;

t[cur].mxpos=t[t[cur].lc].mxpos;

if (t[t[cur].rc].mx>t[cur].mx)

t[cur].mx=t[t[cur].rc].mx,t[cur].mxpos=t[t[cur].rc].mxpos;;

}

int merge(int&x,const int y,const int l,const int r)

{

if (!x||!y)return x|y;

if (!x)x=++pool;

t[x].mx+=t[y].mx;

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

t[x].lc=merge(t[x].lc,t[y].lc,l,mid);

t[x].rc=merge(t[x].rc,t[y].rc,mid+1,r);

if (l==r)t[x].mxpos=l;

else

{

t[x].mx=t[t[x].lc].mx;

t[x].mxpos=t[t[x].lc].mxpos;

if (t[t[x].rc].mx>t[x].mx)

{

t[x].mx=t[t[x].rc].mx;

t[x].mxpos=t[t[x].rc].mxpos;

}

return x;

}

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

{

int np=++tott,p=now;ins(rt[tott],1,n+1,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;

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;

}

pair<int,int>query(const int cur,const int l,const int r,const int L,const int R)

{

if (L<=l&&r<=R)return make_pair(t[cur].mx,-t[cur].mxpos);

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

pair<int,int>ans=make_pair(0,-1e9);

if (L<=mid)ans=query(t[cur].lc,l,mid,L,R);

if (R>mid)ans=max(ans,query(t[cur].rc,mid+1,r,L,R));

return ans;

}

void dfs(const int cur)

{

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

dfs(e[i].too),rt[cur]=merge(rt[cur],rt[e[i].too],1,n+1);

for(vector<ask>::iterator it=store[cur].begin();it!=store[cur].end();++it)

{

ans[(*it).pos]=query(rt[cur],1,n+1,(*it).l,(*it).r);

if (!ans[(*it).pos].first)ans[(*it).pos].second=-(*it).l;

}

void predfs(const int cur)

{

for (int i=1;i<=20;i++)f[cur][i]=f[f[cur][i-1]][i-1];

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

f[e[i].too][0]=cur,predfs(e[i].too);

}

signed main()

{

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

int len=strlen(s+1);

n=read();

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

extend(26,n+1);

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

{

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

int len=strlen(S+1);

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

extend(26,i);

}

for (int i=1,cur=root;i<=len;i++)cur=st[cur].trans[s[i]-'a'],pos[i]=cur;

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

predfs(1);

int m=read();

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

{

int l=read(),r=read(),L=read(),R=read(),cur=pos[R];

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

if (st[f[cur][i]].len>=R-L+1)cur=f[cur][i];

store[cur].push_back((ask){l,r,Pos});

}

dfs(1);

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

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments