P3763 [TJOI2017]DNA(SAM+dfs)

LINK
SAM写法

记得以前是用$FFT$写的,推狮子翻来覆去…

然而这不是被$SAM$秒掉的垃圾题吗??!!

建立$SAM$,直接从根节点去$dfs$

如果自动机上有边转移就不需要花费,否则花费一次字母不同的机会

如果匹配完了串$S$,加上当前节点的出现次数即可

LCP写法

直接枚举 s 0 s_0 s0​中的开始位置$j$,判断$[j,j+|S|-1]$是否满足要求

当然不是一位一位匹配,我们直接跳跃相同的部分

怎么跳??这个可以二分+哈希来跳,也可以开始用后缀数组串起来求$height$数组得到

#include 
using namespace std;
const int maxn = 1e6+10;
int zi[maxn][30],fa[maxn],siz[maxn],len[maxn],las = 1,id = 1,ans = 0,n,m;
char a[maxn],s[maxn];
void insert(int c)
{int p = las, np = ++id; las = id;len[np] = len[p]+1; siz[np] = 1;for( ; p&&!zi[p][c];p=fa[p] )	zi[p][c] = np;if( !p )	fa[np] = 1;else{int q = zi[p][c];if( len[q]==len[p]+1 )	fa[np] = q;else{int nq = ++id; len[nq] = len[p]+1;memcpy( zi[nq],zi[q],sizeof zi[nq] );fa[nq] = fa[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[len[i]]++;for(int i=1;i<=id;i++)	c[i] += c[i-1];for(int i=1;i<=id;i++)	rk[c[len[i]]--] = i;for(int i=id;i>=1;i--)siz[fa[rk[i]]] += siz[rk[i]];
}
void dfs(int u,int l,int ci)
{if( ci>3 )	return;if( u!=1&&l==m+1 )	ans += siz[u];if( l>m )	return;for(int i=0;i<=25;i++){if( !zi[u][i] )	continue;dfs( zi[u][i],l+1,ci+( i!=(s[l]-'A') ) );}
}
int main()
{int t; cin >> t;while( t-- ){cin >> ( a+1 ) >> ( s+1 );n = strlen( a+1 ), m = strlen( s+1 );for(int i=1;i<=n;i++)	insert( a[i]-'A' );chiken_sort();dfs(1,1,0);cout << ans << endl;for(int i=1;i<=id;i++)memset( zi[i],0,sizeof zi[i] ),fa[i] = len[i] = siz[i] = c[i] = rk[i] = 0;ans = 0, las = id = 1;}
}

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