首页 > 代码库 > uva1401 dp+Trie

uva1401 dp+Trie

2024-07-21 23:02:31   224人阅读

这题说的是给了一个长的字符串长度最大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\n",++cas,dp[0]);     }     return 0;}
View Code

 

uva1401 dp+Trie


联系
我们