Gym101194F Mr. Panda and Fantastic Beasts(广义SAM+最短路)-白红宇的个人博客

Gym101194F Mr. Panda and Fantastic Beasts(广义SAM+最短路)

发布日期：2021-06-30 10:32:31 浏览次数：2 分类：技术文章

本文共 6864 字，大约阅读时间需要 22 分钟。

①.标记法

直接对 $n$ 个串建立广义 $S A M$

如果是第一个串插入产生的节点标记为 $0$ ,其余串插入的节点标记为 $1$

然后由于祖先节点都是自己的后缀,如果自己属于第一个串,那么祖先也是第一个串

所以基数排序一遍,把标记传递给祖先节点

于是,每个点是否独立属于第一个串我们就知道了。

我们从自动机的根节点开始 $b f s$ ,保存到达每个点的最短路

第一个搜到的合法节点(只在第一个串出现),就是我们的答案,途经的转移边就是子串

正版广义SAM（特判重复节点版本）

#include 
   
    using namespace std;const int maxn = 1e6+10;int casenum;int zi[maxn][27],fa[maxn],l[maxn],id=1,las=1,f[maxn];char a[maxn];void insert(int c,int ok){
   	int p = las;	if( zi[p][c] )//重复节点,所以我们需要把q,nq都染色,因为这次并没有新建节点!! 	{
   		int q = zi[p][c];		if( l[q]==l[p]+1 )	las = q,f[q] = ok;		else		{
   			int nq = ++id; las = nq;			memcpy( zi[nq],zi[q],sizeof zi[nq] );			fa[nq] = fa[q], l[nq] = l[p]+1; f[nq] = f[q] | ok;			fa[q] = nq;			for( ; p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;		}	}	else	{
   		int np = ++id; las = id;		l[np] = l[p]+1; f[np] = ok; 		for( ; p&&zi[p][c]==0 ;p=fa[p] )	zi[p][c] = np;		if( p==0 )	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[nq] );				l[nq] = l[p]+1, fa[nq] = fa[q]; f[nq] = f[q];				fa[q] = fa[np] = nq;				for( ; p&&zi[p][c]==q; p=fa[p] )	zi[p][c] = nq;			}		}	}}int c[maxn],rk[maxn];void chiken_sort(){
   	for(int i=1;i<=id;i++)	c[l[i]]++;	for(int i=1;i<=id;i++)	c[i] += c[i-1];	for(int i=1;i<=id;i++)	rk[c[l[i]]--] = i;	for(int i=id;i>=1;i--)	{
   		int u = rk[i];		f[fa[u]] |= f[u];	}}void build(int ok){
   	las = 1;	scanf("%s",a+1 ); int n = strlen( a+1 );	for(int i=1;i<=n;i++)	insert( a[i]-'a',ok );}int pre[maxn],vis[maxn];char ans[maxn];void dfs(int ed){
   	if( ed==1 )	return;	dfs( pre[ed] );	printf("%c",ans[ed] );}void solve(){
   	queue
    
     q; q.push( 1 );	int ed = 0;	for(int i=1;i<=id;i++)	vis[i] = 0;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		if( f[u]==0 ) {
    ed = u; break; }		for(int i=0;i<=25;i++)		{
   			int v = zi[u][i];			if( v==0 || vis[v] )	continue;			vis[v] = 1;			ans[v] = 'a'+i; pre[v] = u; q.push( v );		}	}	printf("Case #%d: ",++casenum);	if( ed==0 )	puts("Impossible");	else	{
    dfs(ed); cout << '\n'; }}int main(){
   	int t; cin >> t;	while( t-- )	{
   		int n; cin >> n;		build( 0 );		for(int i=2;i<=n;i++)	build( 1 );		chiken_sort();		solve();				for(int i=1;i<=id;i++)		{
   			memset( zi[i],0,sizeof zi[i] );			f[i] = fa[i] = l[i] = c[i] = rk[i] = 0;		}		las = id = 1;	}}

普通广义 $S A M$ (无特判)

#include 
   
    using namespace std;const int maxn = 1e6+10;int casenum;int zi[maxn][27],fa[maxn],l[maxn],id=1,las=1,f[maxn];char a[maxn];void insert(int c,int ok){
   	int p = las,np = ++id; las = id;	l[np] = l[p]+1; f[np] = ok; 	for( ; p&&zi[p][c]==0 ;p=fa[p] )	zi[p][c] = np;	if( p==0 )	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[nq] );			l[nq] = l[p]+1, fa[nq] = fa[q]; f[nq] = f[q];			fa[q] = fa[np] = nq;			for( ; p&&zi[p][c]==q; p=fa[p] )	zi[p][c] = nq;		}	}}vector
    
     vec[maxn];void dfs_fail(int u){
   	for( auto v:vec[u] )	{
   		dfs_fail(v);		f[u] |= f[v];	}}void build(int ok){
   	las = 1;	scanf("%s",a+1 ); int n = strlen( a+1 );	for(int i=1;i<=n;i++)	insert( a[i]-'a',ok );}int pre[maxn],vis[maxn];char ans[maxn];void dfs(int ed){
   	if( ed==1 )	return;	dfs( pre[ed] );	printf("%c",ans[ed] );}void solve(){
   	queue
     
      q; q.push( 1 );	int ed = 0;	for(int i=1;i<=id;i++)	vis[i] = 0;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		if( f[u]==0 ) {
    ed = u; break; }		for(int i=0;i<=25;i++)		{
   			int v = zi[u][i];			if( v==0 || vis[v] )	continue;			vis[v] = 1;			ans[v] = 'a'+i; pre[v] = u; q.push( v );		}	}	printf("Case #%d: ",++casenum);	if( ed==0 )	puts("Impossible");	else	{
    dfs(ed); cout << '\n'; }}int main(){
   	int t; cin >> t;	while( t-- )	{
   		int n; cin >> n;		build( 0 );		for(int i=2;i<=n;i++)	build( 1 );		for(int i=2;i<=id;i++)	vec[fa[i]].push_back( i );		dfs_fail(1);		solve();				for(int i=1;i<=id;i++)		{
   			vec[i].clear();			memset( zi[i],0,sizeof zi[i] );			f[i] = fa[i] = l[i] = 0;		}		las = id = 1;	}}

②.动态匹配法

我们只把后 $n - 1$ 个串建立广义 $S A M$

拿第一个串在自动机上跑即可

当我们插入完 $i$ 节点后发现失配了,之前的匹配节点是 $x$ ,匹配长度是 $l$

我们就需要往上跳 $f a$ 去匹配,如果仍然没有转移边就重复跳 $f a$

向上跳跃的过程中,我们经过了若干个没有转移边的节点

记这些节点为 $p$ ,其中最短的子串为 $l[fa_p]+1$ ,那么最短 $l[fa_p]+2$ 就会适配(加上当前的 $a_i$ 字符)

最后更新一下就好了

#define others#ifdef poj#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #endif // poj#ifdef others#include 
            
             #endif // others//#define file#define all(x) x.begin(), x.end()using namespace std;#define eps 1e-8const double pi = acos(-1.0);typedef long long LL;typedef unsigned long long ULL;void umax(int &a, int b) { a = max(a, b);}void umin(int &a, int b) { a = min(a, b);}int dcmp(double x) { return fabs(x) <= eps?0:(x > 0?1:-1);}namespace solver { int res = 1e9, pos = 0; string s, t; namespace SAM{ static const int maxnode = 2e6+10;//至少开两倍 static const int maxn = 27; int p, q, np, nq; int cnt, ST_T, len; vector
             
              G; int trans[maxnode][maxn], l[maxnode], fa[maxnode]; int newnode() { int x = ++cnt; memset(trans[x], 0, sizeof trans[x]); fa[x] = 0; l[x] = 0; return cnt; } void init() { cnt = 0; ST_T = newnode(); } void add(int c) { //令当前串为T，新加的字符为x。 p = ST_T; np = ST_T = newnode(); l[np] = l[p] + 1;//令p = ST(T)，新建np = ST(Tx) while(!trans[p][c]&&p) trans[p][c] = np, p = fa[p];//对于p的所有没有标号c的边的祖先v，trans[v][c] = np。 if(!p) fa[np] = 1; //找到p的第一个祖先vp,他有标号c的边，如果没有这样的vp，那么fa[p]=root，结束该阶段。 else { q = trans[p][c];//令q=trans[vp][c] if(l[p] + 1 == l[q]) fa[np] = q;//若l[q] = l[vp] + 1,令fa[np] = q,结束该阶段。 else { nq = newnode(); l[nq] = l[p] + 1;//否则建立新节点nq memcpy(trans[nq],trans[q],sizeof(trans[q]));//trans(nq, *) = trans(q, *) fa[nq] = fa[q]; fa[np] = fa[q] = nq; while(trans[p][c] == q) trans[p][c] = nq, p = fa[p];//对于所有的trans(v, c) == q的p的祖先v, trans(v, c)改为nq。 } } } void build(string &str) { len = str.size(); for(int i = 0; i < len; i++) add(str[i]-'a'); } void solve(string &str) { int x = 0, p = 1; for(int i = 0; i < str.size(); i++) { if(trans[p][str[i]-'a']) { p = trans[p][str[i]-'a']; x = l[fa[p]] + 1; } else { int now = 0; while(p && !trans[p][str[i]-'a']) { //失配,之前的匹配长度为x now = x+1; p = fa[p]; x = l[fa[p]] + 1; } if( now )//保存最短的不可匹配长度 { if(res > now ) { //长度更小 res = now; pos = i; } else if(res == now) { if(s.substr(i - res + 1, res) < s.substr(pos - res + 1, res)) pos = i; } } if(p == 0) { x = 0, p = 1; } else { p = trans[p][str[i]-'a']; x = l[fa[p]]+1; } } } } }; int tt; void solve() { cin >> tt; int f = 0; while(tt--) { res = 1e9; int n; cin >> n; cin >> s; cin >> t; for(int i = 2; i < n; i++) { string tmp; t += 'z'+1; cin >> tmp; t += tmp; } SAM::init(); SAM::build(t); SAM::solve(s); cout<<"Case #"<<++f<<": "; if(res == 1e9) { cout<<"Impossible"<<'\n'; } else { cout<

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116015415 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：2016-2017 ACM-ICPC CHINA-Final C.Mr. Panda and Strips(dp预处理+暴力)

下一篇：2016-2017 ACM-ICPC CHINA-Final F. Mr. Panda and Fantastic Beasts(后缀数组的两种解法)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章