学步园

大意：给出一个有S个不同单词组成的字典和一个字符串。把这个字符串分解成若干个单词的连接，有多少种方法？

思路：令d[i]表示以字符i结束的字符串的分解方案数，即d[i+j] = sum(d[i]) (j为一个单词的长度)，初始化d[0] = 1;把所有单词组成Trie，然后试着在Trie中查找单词即可。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxnode = 4010*100;
const int sigma_size = 26;
const int MAXN = 300010;
const int MOD = 20071027;

char str[MAXN];
int d[MAXN];

struct trie
{
	int ch[maxnode][sigma_size];
	int val[maxnode];
	int sz;
	int idx(char c) { return c - 'a';}
	void init()
	{
		sz = 1;
		memset(ch[0], 0, sizeof(ch[0]));
	}
	void insert(char *s, int v)
	{
		int u = 0, n = strlen(s);
		for(int i = 0; i < n; i++)
		{
			int c = idx(s[i]);
			if(!ch[u][c])
			{
				memset(ch[sz], 0, sizeof(ch[sz]));
				val[sz] = 0;
				ch[u][c] = sz++;
			}
			u = ch[u][c];
		}
		val[u] = v;
	}
	int find(char *s)
	{
		int u = 0;
		for(int i = 0; s[i]; i++)
		{
			int c = idx(s[i]);
			if(!ch[u][c]) return 0;
			u = ch[u][c];
		}
		return val[u];
	}
}Trie;

void read_case()
{
	Trie.init();
	int n;
	scanf("%d", &n);
	while(n--)
	{
		char temp[110];
		scanf("%s", temp);
		Trie.insert(temp, 1);
	}
}

void solve()
{
	read_case();
	memset(d, 0, sizeof(d));
	int len = strlen(str+1);
	d[0] = 1, str[0] = 'x';
	for(int i = 0; str[i]; i++)
	{
		int u = 0;
		for(int j = 1; j <= len; j++)
		{
			int c = Trie.idx(str[i+j]);
			u = Trie.ch[u][c];
			if(!u) break;
			else if(Trie.val[u] == 1)
			{
				d[i+j] += d[i];
				if(d[i+j] >= MOD) d[i+j] %= MOD;
			}
		}
	}
	printf("%d\n", d[len]);
}

int main()
{
	int times = 0;
	while(~scanf("%s", str+1))
	{
		printf("Case %d: ", ++times);
		solve();
	}
	return 0;
}