首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。