cf86C(AC自动机+dp)

Posted on   |   In

题意

给定$m$个字符串 问构造长度为$n$的串的方案数

构造串需满足 对于任意位置 $i$ 都存在一个子区间[l,r] 包含$i$且子区间对应m个串中的任意一个

题解

AC自动机+DP

我们可以设$dp[i][j][k]$ 表示已经构造了长度为$i$的串 且在自动机中第$j$状态 且存在$k$字符属于失配状态

对于每个位置 我们找到其在自动机上 m个串为其后缀的最长的那个串的长度

设加入四种字符其中一个后达到的目的状态为$x$ 当前状态为$y$

那么转移就是

若当前失配的长度$k<maxdis$ 那么 $dp[i+1][x][0]+=dp[i][y][k]$

反之则 $dp[i+1][x][k+1]+=dp[i][y][k]$

复杂度为$O(NM*400)$

代码实现

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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int mod=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int T[MAXN];
typedef struct node{
    int dep,ch[4],fair,pos;
    bool vis;
}node;
int rt,n,m,cnt;
node d[105];
void newnode(int &x,int y){
    x=++cnt;d[x].dep=d[y].dep+1;d[x].fair=0;
    d[x].pos=0;
}
void insert(char str[]){
    int len=strlen(str);int temp=rt;
    for(int i=0;i<len;i++){
	int t=T[str[i]-'A'];
	if(!d[temp].ch[t])newnode(d[temp].ch[t],temp);
	temp=d[temp].ch[t];
    }
    d[temp].vis=1;d[temp].pos=temp;
}

queue<int>que;
void Ac(){
    que.push(rt);
    while(!que.empty()){
	int x=que.front();que.pop();
	for(int i=0;i<4;i++){
	    if(!d[x].ch[i]){d[x].ch[i]=d[d[x].fair].ch[i];continue;}
	    if(!d[x].fair){d[d[x].ch[i]].fair=rt;que.push(d[x].ch[i]);continue;}
	    int temp=d[x].fair;
	    while(temp&&!d[temp].ch[i])temp=d[temp].fair;
	    if(!temp)d[d[x].ch[i]].fair=rt;else d[d[x].ch[i]].fair=d[temp].ch[i];
	    if(d[d[d[x].ch[i]].fair].dep>d[d[d[x].ch[i]].pos].dep)d[d[x].ch[i]].pos=d[d[d[x].ch[i]].fair].pos;
	    que.push(d[x].ch[i]); 	
	}
    }
}

int dp[1005][101][21];
char str[21];

int main(){
    T['A'-'A']=0;T['C'-'A']=1;T['G'-'A']=2;T['T'-'A']=3;
    n=read();m=read();newnode(rt,0);d[rt].dep=0;
    inc(i,1,m)scanf("%s",str),insert(str);
    Ac();dp[0][1][0]=1;
    for(int i=0;i<n;i++){
	for(int j=1;j<=cnt;j++){
	    for(int k=0;k<4;k++){
		int pos=d[j].ch[k];
		//cout<<j<<"===="<<k<<" "<<pos<<" "<<d[j].ch[k]<<endl;
		if(!pos)continue;
		for(int p=0;p<=9;p++){
		    if(d[d[pos].pos].dep>p){
			//cout<<j<<" "<<k<<" "<<pos<<"::: "<<p<<endl;
			dp[i+1][pos][0]+=dp[i][j][p];dp[i+1][pos][0]%=mod;
		    }
		    else{
			dp[i+1][pos][p+1]+=dp[i][j][p];dp[i+1][pos][p+1]%=mod;
		    }
		}
	    }
	}
//		cout<<i+1<<":::"<<endl;
//	for(int j=1;j<=cnt;j++){
//	    for(int k=0;k<=10;k++)cout<<dp[i+1][j][k]<<" ";
//	    cout<<endl;
//	}
    }
    ll ans=0;
    for(int i=1;i<=cnt;i++)ans+=dp[n][i][0],ans%=mod;
    printf("%lld\n",ans);
    return 0;
}