UVaLive3942

发表于 | 分类于 |

题目传送门

Description

给你一条由小写字母组成的长字符串$S$（长度不超过$300000$），再给你$N$（$1\leq N\leq4000$）条短字符串$C_i$（每条长度不超过$100$），用$C_i$组成$S$，问有多少种方法，结果对$20071027$取模。

如：$S$为$abcd$，$C_i$分别为：$a,b,ab,cd$时。那么有$a+b+cd$和$ab+cd$两种方法。

多组测试数据。

Input

每组测试数据：

第一行：一个字符串，$S$ 。

第二行：一个整数，$N$ 。

接下来$N$行：每行一字条符串$C_i$ 。

Output

若干行：

每行格式为：”$Case$ $i$$:$ $ans$”（不含引号）。

Solution

看到方案数就可以想到用$DP$，这题有点像背包问题，用$F_i$表示：从$S_0$到$S_i$有多少种组合方法。则：

$Fi$=sum{$F{ i-len(C_j) }$|$Cj=F{ i-lenC_J…i }$}

显然每次求都搜索一遍$C_i$匹配一遍会超时时了。

这就要用到$trie$了。

把$C$全部组织成一棵$trie$，枚举$S$的起始点$i$，在$trie$上从$S_i$开始匹配，若匹配到$S_j$时可以匹配到一个完整的$Ck$就可以用$F{j-len(C_k)}$更新$F_j$了。

因为$len(C_i)$不超过$100$，所以在$trie$上匹配的次数不超过$100$，不会超时。

Code

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxL=300100;
const int maxl=110;
const int maxn=4010;
char str1[maxL],word[maxn][maxl];
int trie[maxn*maxl][30],sz,check[maxn*maxl],q,L; 
int n;
long long int f[maxL];
int T(char a)
{return int(a-'a');}
void maketrie(int x)
{
	int u=0,N=strlen(word[x]);
	
	for(int i=0;i<N;i++)
	{
		if(!trie[u][T(word[x][i])])
		{
			memset(trie[++sz],0,sizeof(trie[sz]));
			check[sz]=0;
			trie[u][T(word[x][i])]=sz;
		}
		u=trie[u][T(word[x][i])];
	}
	check[u]++;
}
void find(int x)
{
	int u=0;
	for(int i=1;trie[u][T(str1[x])]&&x<L;i++,x++)
	{
		u=trie[u][T(str1[x])];
		if(check[u])
			f[x+1]=(f[x+1]+f[x+1-i]*check[u])%20071027;
	}
}
void init()
{
	sz=0;
	memset(f,0,sizeof(f));
	memset(check,0,sizeof(check));
	memset(trie[0],0,sizeof(trie[0]));
	f[0]=1;
	q++;
}
int main()
{
	while(scanf("%s",str1)==1)
	{
		init();
		L=strlen(str1);
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%s",word[i]);
		for(int i=1;i<=n;i++) maketrie(i);
		for(int i=0;i<L;i++) find(i);
		printf("Case %d: %lld\n",q,f[L]);
	}
	return 0;
}