「LA-3942」Remember the Word (Trie树+DP)

发表于 | 分类于 ，

「LA-3942」Remember the Word
Trie+DP，求解若干个模式串组合构成目标串的方案数

题意

给定一个由小写字母组成的长字符串$S(1≤|S|≤300000)$和$N(1≤N≤4000)$条短字符串$C_i(1≤|C_i|≤100)$，求用短字符串构成长字符串的方案数，结果对$20071027$取模。

解法

对于目标串$S$，构建数组$dp[i]$，表示位于$i$时，字符串的后缀$S’$的组成方案数。

对于模式串$C_i$，若其能与$S’$长度为$len$的前缀子串匹配，则有状态转移方程$dp[i]+=dp[i+len+1]$，由于$|C_i|≤100$，则最多只需枚举长度为$100$的前缀子串。

考虑对模式串$C_i$建立Trie树，枚举后缀子串$S’$即可求解。

代码

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=3e5+10;
const int mod=20071027;

char s[maxn];
int dp[maxn],len;

int trie[maxn][30],tot;
bool val[maxn];

void insert_ch(char *str)
{
	int len=strlen(str);
	int root=0;
	for(int i=0;i<len;i++)
	{
		int id=str[i]-'a';
		if(!trie[root][id]) trie[root][id]=++tot;
		root=trie[root][id];
	}
	val[root]=true;
}

void find_ch(char *str,int pos)
{
	int root=0,ans=0;
	for(int i=pos;i<len&&i<=pos+100;i++)
	{
		int id=str[i]-'a';
		if(!trie[root][id]) return;
		root=trie[root][id];
		if(val[root]) (dp[pos]+=dp[i+1])%=mod;
	}
}

void init()
{
	memset(trie,0,sizeof trie);
	memset(val,0,sizeof val);
	memset(dp,0,sizeof dp);
	tot=0;
}

int main()
{
    char t[105];
    int n,cnt=0;
    while(scanf("%s",s)!=EOF)
    {
        init();
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",t);
            insert_ch(t);
        }
        len=strlen(s);
        dp[len]=1;
        for(int i=len-1;i>=0;i--) find_ch(s,i);
        printf("Case %d: %d\n",++cnt,dp[0]);
    }
    return 0;
}