首页 > 代码库 > Tire 字典树&& uva1401

Tire 字典树&& uva1401

题意:给一个长字符串s(1<|s|<300000),和n(n<4000)个单词,求出有多少种把s分成单词的方法(白书P209)。

打模板!

#include<cstdio>#include<cstring>#define MOD 20071027#define maxnode 4010*101#define MAXLEN 300005#define sigema_size 26int ca=0,S,d[MAXLEN];char str[MAXLEN],tmp[105];struct Trie{    int sz;    int ch[maxnode][sigema_size];    int val[maxnode];    void init() {sz=1;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));}    int idx(char c) {return c-a;}    void insert(char *s)    {        int u=0;        for(int i=0;s[i];++i)        {            int c=idx(s[i]);            if(!ch[u][c])            {                memset(ch[sz],0,sizeof(ch[c]));                ch[u][c]=sz++;            }            u=ch[u][c];        }        val[u]=1;    }    int find(char *s,int a)    {        int u=0,ans=0;        for(int i=a;s[i];++i)        {            int c=idx(s[i]);            if(!ch[u][c]) return ans;            u=ch[u][c];            if(val[u]) ans=(ans+d[i+1])%MOD;        }        return ans;    }}trie;void solve(){    int n=strlen(str);    d[n]=1;    for(int i=n-1;i>=0;--i) d[i]=trie.find(str,i);    printf("Case %d: %d\n",++ca,d[0]);}int main(){    while(~scanf("%s",&str))    {        trie.init();        scanf("%d",&S);        for(int i=0;i<S;++i){scanf("%s",tmp);trie.insert(tmp);}        solve();    }    return 0;}