题目链接：

差点就被这个题目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
      
       #include
       
        using namespace std;const int maxnode = 4000*100+10;const int sigma_size = 26;struct Trie{    int ch[maxnode][sigma_size];    int val[maxnode];    int sz;     ///节点总数    void clear()    {        sz = 1;        memset(ch[0],0,sizeof(ch[0]));    }    int idx(char c)    {        return c-'a';    }    void insert(const 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;     }    ///找字符串s不超过len的前缀    void find_prefixes(const char *s, int len, vector
        
         & ans)    {        int u = 0;        for(int i = 0; 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] != 0) ans.push_back(val[u]); // 找到一个前缀        }    }};#include
         
          const int maxl = 300000+10;const int maxw = 4000+10;const int maxwl = 100+10;const int MOD = 20071027;int d[maxl],len[maxw];char text[maxl],word[maxwl];Trie trie;int main(){    //freopen("in.txt","r",stdin);    int cases =1 ;    int s;    while(scanf("%s%d",text,&s)==2)    {        trie.clear();        for(int i=1; i<=s; i++)        {            scanf("%s",word);            len[i] = strlen(word);            trie.insert(word,i);        }        memset(d,0,sizeof(d));        int L = strlen(text);        d[L] = 1;        for(int i=L-1; i>=0; i--)        {            vector
          
            p;            trie.find_prefixes(text+i,L-i,p);            for(int j=0; j