P5284 [十二省联考2019]字符串问题(技巧,SAM的前缀和连边)

LINK

考虑每个 A i A_i Ai​向 A j A_j Aj​连边,当且仅当存在一个被 A i A_i Ai​支配的串 B z B_z Bz​,使得 B z B_z Bz​为 A j A_j Aj​的前缀

这样得到了一个图,只需对这个图拓扑排序求最长路即可.

$T1$

先可以对所有的支配关系由$A$连向$B$,费用为$0$(此时$B$串相当于一个中转点)

那么现在只需要考虑 B i B_i Bi​是哪些$A$串的前缀然后连边

可以很容易的知道,在后缀自动机上,父亲是儿子的后缀

如果我们对反串建$SAM$,反串$SAM$中父亲是儿子的后缀,意味着原串中父亲是儿子的前缀

所以只需要由 B i B_i Bi​向所有子树中的$A$串节点连边即可

此时复杂度降为 O ( n 2 ) O(n^2) O(n2),究其原因还是边太多了不能暴力连

40分代码

$T2$

注意到$SAM$中的一个节点对应多个子串,我们把这些子串按照长度排序

若长度相同,则按$A$类串在前,$B$类串在后的顺序排序

设排序后变成这个样子 a 1 , a 2 , b 1 , a 3 , b 2 , a 4 a_1,a_2,b_1,a_3,b_2,a_4 a1​,a2​,b1​,a3​,b2​,a4​

那么我们就连边 ( i , a 1 ) , ( i , a 2 ) , ( i , b 1 ) , ( b 1 , a 3 ) , ( b 1 , b 2 ) , ( b 2 , a 4 ) (i,a_1),(i,a_2),(i,b_1),(b_1,a_3),(b_1,b_2),(b_2,a_4) (i,a1​),(i,a2​),(i,b1​),(b1​,a3​),(b1​,b2​),(b2​,a4​)

其中$i$表示$SAM$中的这个节点,并无实际意义,只是起到祖先和儿子的连通作用

设祖先有个$B$类串能转移到 a 1 a_1 a1​,那么也必然能转移到 a 2 a_2 a2​,因为他们互为前缀关系

然后,祖先中的$B$类串也可以不选择 a 1 , a 2 a_1,a_2 a1​,a2​,而是转移到 b 1 b_1 b1​,在下面的串再找机会

所以我们的连边策略就是记录一个$lastb$表示上次的最长$B$类串

然后$lastb$向遇到的所有串都连边,直到遇到更长的$B$类串再更新$lastb$

非常厉害的技巧,类似前缀和连边

#include 
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
int zi[maxn][27],fa[maxn],l[maxn],ed[maxn],id = 1, las = 1;
char s[maxn];
int le,m,na,nb;
void insert(int c)
{int p = las, np = ++id; las = id;l[np] = l[p]+1; for( ; p&&zi[p][c]==0;p=fa[p] )	zi[p][c] = np;if( !p 	)	fa[np] = 1;else{int q = zi[p][c];if( l[q]==l[p]+1 )	fa[np] = q;else{int nq = ++id;memcpy( zi[nq],zi[q],sizeof zi[q] );fa[nq] = fa[q], l[nq] = l[p]+1;fa[np] = fa[q] = nq;for( ; p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;	}}
}
vector<int>vec[maxn];
int up[maxn][22],in[maxn],lst[maxn],isa[maxn],sz;
int a[maxn],b[maxn];
ll dis[maxn];
bool com(int a,int b)
{return l[a]>l[b]||(l[a]==l[b]&&isa[a]>isa[b] );
}
void isok(int aorb)
{int L,R; scanf("%d%d",&L,&R);int x = ed[L];for(int i=21;i>=0;i--)if( up[x][i] && l[up[x][i]]>=R-L+1 )	x = up[x][i];isa[++sz] = aorb, l[sz] = R-L+1;vec[x].push_back( sz ); in[sz]++;
}
void find_A_B()
{sz = id;scanf("%d",&na );for(int i=1;i<=na;i++)	isok( 1 ),a[i] = sz;scanf("%d",&nb );for(int i=1;i<=nb;i++)	isok( 0 ),b[i] = sz;for(int i=1;i<=id;i++)	sort( vec[i].begin(),vec[i].end(),com );for(int i=1;i<=id;i++){int last = i;for(int j=vec[i].size()-1;j>=0;j--){int now = vec[i][j]; vec[last].push_back( now ); in[now]++;if( !isa[now] )	last = now;}lst[i] = last;}for(int i=2;i<=id;i++)vec[lst[fa[i]]].push_back( i ),in[i]++;for(int i=1;i<=sz;i++)if( !isa[i] )	l[i] = 0;scanf("%d",&m );for(int i=1;i<=m;i++){int L,R; scanf("%d%d",&L,&R );vec[a[L]].push_back( b[R] ); in[b[R]]++;}
}
void tuopu()
{queue<int>q; for(int i=1;i<=sz;i++)if( !in[i] )	q.push( i );int shu = 0; ll ans = 0;while( !q.empty() ){int u = q.front(); q.pop();shu++; ans = max( ans,dis[u]+l[u] );for(auto v:vec[u] ){dis[v] = max( dis[v],dis[u]+l[u] );if( --in[v]==0 )	q.push( v );}	}if( shu!=sz )	printf("-1\n");else	printf("%lld\n",ans );
}
void init()
{for(int i=1;i<=id;i++){memset( zi[i],0,sizeof zi[i] );l[i] = fa[i] = 0;}for(int i=0;i<=sz;i++){vec[i].clear();isa[i] = 0;in[i] = dis[i] = l[i] = lst[i] = 0;}id = las = 1; sz = 0;
}
int main()
{int T; cin >> T;while( T-- ){scanf("%s",s+1 ); le = strlen( s+1 );for(int i=le;i>=1;i--)insert( s[i]-'a' ), ed[i] = las;for(int i=1;i<=id;i++)	up[i][0] = fa[i];for(int i=1;i<=21;i++)for(int j=1;j<=id;j++)up[j][i] = up[up[j][i-1]][i-1];find_A_B();tuopu();init();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！