首页 > 代码库 > LA 3942 Remember the Word 字典树+dp

LA 3942 Remember the Word 字典树+dp

 

#include <cstdio>#include <cstring>using namespace std;#define mod 20071027int dic[401000][28],val[401000];char str[301000];int dp[301000];int s,sz;char T[110];void insert(char *ch){    int u=0,len=strlen(ch);    for(int i=0;i<len;i++)    {        int id=ch[i]-a;        if(!dic[u][id])        {            memset(dic[sz],0,sizeof(dic[sz]));            dic[u][id]=sz++;        }        u=dic[u][id];    }    val[u]=1;}int main(){    int sum=0;    while(scanf("%s",str)!=EOF)    {        sum++;        memset(val,0,sizeof(val));        sz=1;        memset(dic[0],0,sizeof(dic[0]));        memset(dp,0,sizeof(dp));        scanf("%d",&s);        for(int i=0;i<s;i++)        {            scanf("%s",T);            insert(T);        }        int len=strlen(str);        dp[len]=1;        for(int i=len-1;i>=0;i--)        {            int u=0;            int tot=0;            for(int j=i;j<len;j++)            {                tot++;                int id=str[j]-a;                if(!dic[u][id]) break;                u=dic[u][id];                if(val[u]) dp[i]=(dp[i]+dp[i+tot])%mod;             }        }        //for(int i=0;i<=len;i++) printf("%d ",dp[i]);        printf("Case %d: %d\n",sum,dp[0]);    }    return 0;}

 

LA 3942 Remember the Word 字典树+dp