【[TJOI2017]DNA】

[题目][https://www.lydsy.com/JudgeOnline/problem.php?id=4892]

好像用\(SAM\)做的都是\(dfs\)啊

其实这里也是搜索

如果用\(SAM\)来做非常好理解，就是从\(SAM\)上匹配这个字符串，允许有不超过三条转移边不一样

于是\(dfs\)做法非常显然了，就是爆搜这三条不一样的转移边在哪里，但是复杂度看起来好像很迷，可能是\(\binom{n}{3}\)也就是\(O(n^3)\)级别

但是由于很多情况下选择某一条转移甚至都无法在\(SAM\)上有一个长度为\(n\)的匹配，所以\(dfs\)非常的快

这里写的是一个\(bfs\)，但是长得和\(dp\)有点像？

设\(f[i][j][k]\)表示在\(SAM\)上跑了\(i\)位跑到了\(j\)这个节点，\(k\)次个位置不一样是否可行，显然的转移就是枚举下一个是走\(A,C,G,T\)

发现这个数组可以滚动，之后就滚动好了

滚动的同时还需要滚动两个栈，用来存储有用的状态，其实就是广搜里的队列了

还有一个小剪枝，我们提前处理出每一个节点往下跑出来的最长路，我们可以根据这个快速判断出一个状态是否可行

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 200005

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

int Test,lst,cnt,num,n,top[2],tot,o;

struct St {int a,b;} st[2][maxn];

struct E{int v,nxt;} e[maxn<<1];

char S[maxn>>1],T[maxn>>1];

int son[maxn][4],fa[maxn],sz[maxn],len[maxn],head[maxn],mx[maxn],q[maxn],r[maxn],f[maxn][4];

inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}

void dfs(int x) {for(re int i=head[x];i;i=e[i].nxt) dfs(e[i].v),sz[x]+=sz[e[i].v];}

inline int solve(char c) {if(c=='A') return 0;if(c=='C') return 1;if(c=='G') return 2;return 3;}

inline void ins(int c)

{

	int f=lst,p=++cnt; lst=p;

	len[p]=len[f]+1,sz[p]=1;

	while(f&&!son[f][c]) son[f][c]=p,f=fa[f];

	if(!f) {fa[p]=1;return;}

	int x=son[f][c];

	if(len[f]+1==len[x]) {fa[p]=x;return;}

	int y=++cnt;

	len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;

	for(re int i=0;i<4;i++) son[y][i]=son[x][i];

	while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];

}

int main()

{

	scanf("%d",&Test);

	while(Test--)

	{

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

		for(re int i=1;i<=cnt;i++)

			r[i]=head[i]=mx[i]=len[i]=fa[i]=sz[i]=son[i][0]=son[i][1]=son[i][2]=son[i][3]=0;

		top[0]=top[1]=0;

		lst=cnt=1,num=0;

		n=strlen(S+1);

		for(re int i=1;i<=n;i++) S[i]=solve(S[i]),ins(S[i]);

		for(re int i=2;i<=cnt;i++) add(fa[i],i); dfs(1);

		num=tot=o=0;

		for(re int i=1;i<=cnt;i++) head[i]=0;

		for(re int i=1;i<=cnt;i++)

			for(re int j=0;j<4;j++) if(son[i][j]) add(son[i][j],i),r[i]++;

		for(re int i=1;i<=cnt;i++) if(!r[i]) q[++tot]=i;

		for(re int i=1;i<=tot;i++)

			for(re int j=head[q[i]];j;j=e[j].nxt)

			{r[e[j].v]--; mx[e[j].v]=max(mx[e[j].v],mx[q[i]]+1);if(!r[e[j].v]) q[++tot]=e[j].v;}

		n=strlen(T+1);

		for(re int i=1;i<=n;i++) T[i]=solve(T[i]);

		memset(f,0,sizeof(f));

		st[0][++top[0]]=(St){1,0};

		for(re int i=1;i<=n;i++,o^=1)

		{

			for(re int j=1;j<=top[o];j++)

				f[st[o][j].a][st[o][j].b]=0;

			top[o^1]=0;

			for(re int j=1;j<=top[o];j++)

			{

				int x=st[o][j].a,y=st[o][j].b;

				for(re int k=0;k<4;k++)

				if(son[x][k]&&k!=T[i]&&y<3)

				{

					if(mx[son[x][k]]+i<n) continue;

					if(!f[son[x][k]][y+1]) st[o^1][++top[o^1]]=(St){son[x][k],y+1},f[son[x][k]][y+1]=1;

				}

				int k=T[i];

				if(!son[x][k]||mx[son[x][k]]+i<n) continue;

				if(!f[son[x][k]][y]) st[o^1][++top[o^1]]=(St){son[x][k],y},f[son[x][k]][y]=1;

			}

		}

		int ans=0;

		for(re int i=2;i<=cnt;i++) if(f[i][0]||f[i][1]||f[i][2]||f[i][3]) ans+=sz[i];

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

【[TJOI2017]DNA】

最新文章

热门文章