本文主要是介绍UVA 3942 Remember the Word(Trie树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题目大意：给出一个由s个不同的单词组成的字典和一个长的字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？比如，有4个单词a, b, cd, ab,则abcd可以有两种分解的方法：a+b+cd 和 ab+cd。
第一次接触Trie树，有些不是很理解，暂时记录下来 ，作为一个模板。
//Trie树+dp
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxnode 4000*100+100
#define sigma_size 26
#define mod 20071027
char s[300100];
int dp[300110];
struct Trie
{int ch[maxnode][sigma_size];int val[maxnode];int sz;//节点总数void init(){sz=1; memset(ch[0],0,sizeof(ch[0])); val[0]=0;}int idx(char c) { return c-'a'; }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; //中间节点的附加信息为0ch[u][c]=sz++;//新建节点}u=ch[u][c]; //往下走}val[u]=n;//表示这个节点结束了，看题意要求取值}void find(char *s,int st,int l){int u=0;for(int i=0;i<l;i++){int c=idx(s[i]);if(!ch[u][c]) return ;u=ch[u][c];if(val[u]) dp[st]=(dp[st]+dp[st+val[u]])%mod;}return ;}
};
Trie word;
int main()
{// printf("%d**\n",maxnode);int cas=1;while(~scanf("%s",s)){memset(dp,0,sizeof(dp));word.init();int len=strlen(s);int n;scanf("%d",&n);char c[110];for(int i=0;i<n;i++){scanf("%s",c);word.insert(c,1);}dp[len]=1;for(int i=len-1;i>=0;i--){word.find(s+i,i,len-i);}printf("Case %d: %d\n",cas++,dp[0]%mod);}return 0;
}这篇关于UVA 3942 Remember the Word(Trie树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
