（trie）UVALive
设d[i]表示从下标i的字符开始的字符串的分解方法数，显然有倒序的递推公式。
需要求每个位置开始是否能组成模式串的前缀，才可以建立正确的递推。
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <queue> 8 #include <set> 9 #include <map> 10 #include <list> 11 #include <vector> 12 #include <stack> 13 #define mp make_pair 14 #define MIN(a,b) (a>b?b:a) 15 #define rank rankk 16 //#define MAX(a,b) (a>b?a:b) 17 typedef long long ll; 18 typedef unsigned long long ull; 19 const int MAX=3e5+5; 20 const int INF=1e9+5; 21 const int B=1024;//桶的大小 22 const double M=4e18; 23 const int MAX_NODE=MAX; 24 const int sigma_size=30; 25 using namespace std; 26 //const int MOD=1e9+7; 27 const int MOD=20071027; 28 typedef pair<int,int> pii; 29 const double eps=0.000000001; 30 31 struct Trie 32 { 33 int ch[MAX_NODE][sigma_size];//点数、“字母”数 34 int val[MAX_NODE]; 35 int num;//结点总数 36 Trie(){num=1;memset(ch[0],0,sizeof(ch[0]));}//初始时仅有根节点 37 void clear() { num = 1; memset(ch[0], 0, sizeof(ch[0])); } 38 int idx(char c)//返回对应字符的编号 39 { 40 return c-'a'; 41 } 42 /* 43 插入字符串s,附加信息为v。注意v必须非0，因为0代表：本结点不是单词结点 44 */ 45 void insert(const char *s,int v) 46 { 47 int u=0,len=strlen(s); 48 for(int i=0;i<len;i++) 49 { 50 int c=idx(s[i]); 51 if(!ch[u][c])//结点不存在 52 { 53 memset(ch[num],0,sizeof(ch[num])); 54 val[num]=0;//中间节点的附加信息为0 55 ch[u][c]=num++;//新建结点 56 } 57 u=ch[u][c];//往下走 58 } 59 val[u]=v;//字符串的最后一个字符的附加信息为v 60 } 61 /* 62 查询字符串的“附加信息” 63 查询过程中间中断返回0 64 */ 65 int check(char *s) 66 { 67 int u=0,len=strlen(s); 68 for(int i=0;i<len;i++) 69 { 70 int c=idx(s[i]); 71 if(!ch[u][c]) 72 return 0; 73 u=ch[u][c]; 74 } 75 return val[u]; 76 } 77 /* 78 找字符串s的长度不超过len的前缀 79 */ 80 void find_prefixes(const char *s,int len,vector <int> &ans) 81 { 82 int u=0; 83 for(int i=0;i<len;i++) 84 { 85 if(s[i]=='