UVALive - 3942 Remember the Word （Trie）

本文主要是介绍UVALive - 3942 Remember the Word （Trie），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路：转化为Trie树的形式储存，用d(i)表示字符从i开始的字符串的分解方案，每次搜索到一个单词末的时候就可以累加了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxnode = 300001;
const int sigma_size = 26;
const int mod = 20071027;char str[maxnode];
int dp[maxnode],len;struct Trie{int ch[maxnode][sigma_size];int val[maxnode];int sz;void init_Trie(){sz = 1;memset(ch[0],0,sizeof(ch[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;ch[u][c] = sz++;}u = ch[u][c];}val[u] = v;}
}tree;int Search(int x){if (dp[x] >= 0)return dp[x];int p = 0;int temp,sum = 0;for (int i = x; i < (x+100) && i < len; i++){temp = str[i] - 'a';if (!tree.ch[p][temp])break;p = tree.ch[p][temp];if (tree.val[p])sum += (Search(i+1) % mod);}return  dp[x] = sum % mod;
}int main(){int t = 1,n;char temp[101];while (scanf("%s",&str[0]) != EOF){len = strlen(str);memset(dp,-1,sizeof(dp));tree.init_Trie();scanf("%d",&n);for (int i = 0; i < n; i++){scanf("%s",temp);tree.insert(temp,1);}dp[strlen(str)] = 1;printf("Case %d: %d\n",t++,Search(0));}return 0;
}

这篇关于UVALive - 3942 Remember the Word （Trie）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---