[LA3942]Remember the Word

题目（vjudge）
首先要明白这题是dp，
用dp[i]表示从i开始的字符串有多少种分解方法，
转移方程很简单，dp[i]+=dp[i+strlen(x)] | x串为当前串的前缀。
但是我们不会去枚举每个x串，否则时间爆炸。
解决方法就是将所有x串加到一棵Trie里面，
然后用i串去查找，只要到了某个节点上有x串，就执行转移方程。
完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define N 300010
using namespace std;
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
const int mod=20071027LL;
int S,L;
int dp[N];
struct Trie{
	int ch[N+100005][30];
	int val[N+100005];
	int siz;
	void data_clear(){siz=1;memset(ch,0,sizeof ch);memset(val,0,sizeof val);}
	int tr(char x){return x-'a';}
	void charin(char *s,int v)
	{
		int u=0;
		for (int i=0;i<v;++i)
		{
			int c=tr(s[i]);
			if (!ch[u][c])
			{
				memset(ch[siz],0,sizeof ch[siz]);
				val[siz]=0;
				ch[u][c]=siz++;
			}
			u=ch[u][c];
		}
		val[u]=v;
	}
	void query(char *s,int x)
	{
		int u=0;
		for (int i=x;i<L;++i)
		{
			int c=tr(s[i]);
			if (!ch[u][c]) break;
			u=ch[u][c];
			if (val[u]) dp[x]+=dp[x+val[u]],dp[x
		}
	}
}trie;
char s[N];
int main()
{
	int kas=0;
	while (scanf(
	{
		L=strlen(s);
		memset(dp,0,sizeof dp);
		trie.data_clear();
		read(S);
		char s0[105];
		for (int i=1;i<=S;++i)
		{
			scanf(
			trie.charin(s0,strlen(s0));
		}
		dp[L]=1;
		for (int i=L-1;i>=0;--i) trie.query(s,i);
		printf("Case
	}
	return 0;
}