FJOI 2016 所有公共子序列问题（序列自动机+dp）

发表于 |
字数统计: 747字 | 阅读时长 ≈ 4min

【FJOI2016】所有公共子序列问题

问题描述
这里写图片描述

输入格式

输出格式
这里写图片描述

样例输入

6 6
GCTACT
GATCCT
1

样例输出

A
AC
ACT
ATC
CC
CCT
CTG
GA
GAC
GACT
GAT
GC
GCC
GCCT
GCT
GT
GTC
GTCT
GTTT
TC
TCT
TT
26

提示

1≤m,n≤3010

处理子序列问题，需要用到序列自动机。简单的来说，就是记录$son[i][j]$表示从第$i$个位置往后，第一个$j$出现的位置，容易发现，从根出发的一条路径代表了原串的一个子序列。

对于第一问，构建了自动机后直接同时在两个自动机上跑，边跑边输出就行了。

对于第二问，在序列自动机上DP，子序列个数就是从根出发的路径数，在DAG上DP一下就行了。

考虑一下就能发现，此题答案可能非常大，需要高精度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 3020
using namespace std;
const ll mod=1e9;
struct Big
{
	ll *S,cur;
	void Init()
	{
		S=new long long[20];
		for(int i=0;i<20;i++)S[i]=0;
	}
	void Output()
	{
		printf("%lld",S[cur]);
		for(ll i=cur-1;i>=0;i--)printf("%09lld",S[i]);
	}
	void add(ll k)
	{
		S[0]+=k;ll i=0;
		while(S[i]>=mod)S[i+1]+=S[i]/mod,S[i++]%=mod;
		while(S[cur+1])cur++;
	}
	void Add(const Big& o)
	{
		ll i,r=max(o.cur,cur);
		for(i=0;i<=r;i++)
		{
			S[i]+=o.S[i];
			if(S[i]>=mod)S[i+1]+=S[i]/mod,S[i]%=mod;
		}
		cur=min(r+3,19ll);while(cur&&S[cur]==0)cur--;
	}
};
struct PAM
{
	int son[N][56],las[56],nex[N],tot,rt;
	PAM()
	{
		tot=rt=1;
		for(int i=0;i<52;i++)las[i]=rt;
	}
	void Ins(int c)
	{
		tot++;nex[tot]=las[c];
		for(int i=0;i<52;i++)
		for(int j=las[i];j&&!son[j][c];j=nex[j])son[j][c]=tot;
		las[c]=tot;
	}
}A,B;
ll Gid(char c)
{
	if(c>='a'&&c<='z')return c-'a'+26;
	return c-'A';
}
ll Gchar(ll x)
{
	if(x<26)return x+'A';
	return x-26+'a';
}
ll m,n,ty;
Big F[N][N];
bool vis[N][N];
char X[N],Y[N],s[N];
void Get2(ll x,ll y,ll step)
{
	if(x==0||y==0)return;
	for(int i=0;i<step;i++)putchar(s[i]);puts("");
	for(int i=0;i<52;i++)
	{
		s[step]=Gchar(i);
		Get2(A.son[x][i],B.son[y][i],step+1);
	}
}
void Get1(ll x,ll y)
{
	if(vis[x][y])return;
	F[x][y].Init();
	F[x][y].add(1);
	vis[x][y]=1;
	for(int i=0;i<52;i++)
	{
		if(A.son[x][i]==0||B.son[y][i]==0)continue;
		Get1(A.son[x][i],B.son[y][i]);
		F[x][y].Add(F[A.son[x][i]][B.son[y][i]]);
	}
}
int main()
{
	int i,j,k;
	scanf("%lld%lld",&n,&m);
	scanf("%s%s",X,Y);
	for(i=0;i<n;i++)A.Ins(Gid(X[i]));
	for(i=0;i<m;i++)B.Ins(Gid(Y[i]));
	scanf("%lld",&ty);
	if(ty==1)Get2(1,1,0);
	Get1(1,1);
	F[1][1].Output();
}