uva1401 dp+Trie

这题说的是给了一个长的字符串长度最大300000，又给了4000个单词 单词的长度不超过100.计算这个字符串能组成多少种不同单词的组合，求出方案总数。dp[i]以第i个字符为开始的字符串能有多少种的组成方案，这样每次去比较肯定是会超时的，然后可以用Trie树去优化，这样最多枚举100位种比4000位来得快很多

#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
const int maxn = 100*4000+10;
const int signma_size =26;
const int mod = 20071027;
struct Trie{
    int ch[maxn][signma_size];
    int val[maxn];
    int sz;
    Trie(){ sz=1; memset(ch[0],0,sizeof(ch[0]));}
    int idx(char c){  return c-'a'; }
    void clear(){   sz=1;  memset(ch[0],0,sizeof(ch[0])); }
    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]==0){
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
             }
             u=ch[u][c];
        }
        val[u]=v;
    }
    void find(char *s,int n,vector<int> &va)
    {
          int u=0;
          for(int i=0; i<n; ++i){
               int c=idx(s[i]);
               if(ch[u][c]==0) break;
               u=ch[u][c];
               if(val[u]!=0) va.push_back(val[u]);
          }
    }
}A;
char text[300005],str[4005][105];
int Len[4005],dp[300005];
int main()
{
     int S,cas=0;
     while(scanf("%s%d",text,&S)==2){
         A.clear();
         int n=strlen(text);
         for(int i=1; i<=S; i++){
            scanf("%s",str[i]);
            A.insert(str[i],i);
            Len[i]=strlen(str[i]);
         }
         dp[n]=1;
         vector<int> Val;
         for(int i=n-1; i>=0; i--){

             A.find(text+i,n-i,Val);
             dp[i]=0;
             int L=Val.size();
             for(int j=0; j<L; ++j){
                  int t=Val[j];
                  dp[i]=( dp[i] + dp[ i+Len[ t ] ])%mod;
             }
            Val.clear();
         }
         printf("Case %d: %d
",++cas,dp[0]);
     }
     return 0;
}