差点就被这个题目RE疯掉(ノへ￣、)。
字典树：保存字符串集合。
用一个二维数组ch[i][j] 保存节点i,到标号j的叶子节点是否存在。一般val[i] 表示节点 i 对应的附加权值。
这个题目，给一个字典，一个文本，看文本可以有多少种分解方法。
用DP做，DP方程 dp[i] = sum(dp[i+len[x]]) ; 从后往前。
dp[i] 是从字符 i 开始的后缀数组的分解方案， x 是一个单词，是从 i 以后的单词
我RE的地方是ch数组用的char型，然后我一直查数组范围，LRJ的代码，我比照了好久Ｏ(≧口≦)Ｏ。
#include<cstring>
#include<vector> using namespace std; const int maxnode = *+;
const int sigma_size = ; struct Trie
{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz; ///节点总数
void clear()
{
sz = ;
memset(ch[],,sizeof(ch[]));
} int idx(char c)
{
return c-'a';
} void insert(const char *s, int v)
{
int u = , n = strlen(s);
for(int i = ; i < n; i++)
{
int c = idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz], , sizeof(ch[sz]));
val[sz] = ;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = v;
} ///找字符串s不超过len的前缀
void find_prefixes(const char *s, int len, vector<int>& ans)
{
int u = ;
for(int i = ; i < len; i++)
{
if(s[i] == '\0') break;
int c = idx(s[i]);
if(!ch[u][c]) break;
u = ch[u][c];
if(val[u] != ) ans.push_back(val[u]); // 找到一个前缀
}
}
}; #include<cstdio>
const int maxl = +;
const int maxw = +;
const int maxwl = +;
const int MOD = ; int d[maxl],len[maxw];
char text[maxl],word[maxwl];
Trie trie; int main()
{
//freopen("in.txt","r",stdin);
int cases = ;
int s;
while(scanf("%s%d",text,&s)==)
{
trie.clear();
for(int i=; i<=s; i++)
{
scanf("%s",word);
len[i] = strlen(word);
trie.insert(word,i);
}
memset(d,,sizeof(d));
int L = strlen(text);
d[L] = ;
for(int i=L-; i>=; i--)
{
vector<int> p;
trie.find_prefixes(text+i,L-i,p);
for(int j=; j<p.size(); j++)
{
d[i] = (d[i]+d[i+len[p[j]]])%MOD;
}
}
printf("Case %d: %d\n",cases++,d[]);
}
return ;
}