题意：给你一个有S个不同单词组成的字典和一个长字符串，把这个字符串分解成若干个单词的连接，有多少种方法
思路：转化为Trie树的形式储存，用d(i)表示字符从i开始的字符串的分解方案，每次搜索到一个单词末的时候就可以累加了
#include#include #include #include 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; }