首页 > 代码库 > Trie
Trie
uva1401 这题说的是给出一个由S个不同单词组成的字典和一个长字符串.把这个字符串分解成若干个单词的连接(单词可以重复使用),有多少种方法? 比如有4 个单词 a b cd ab 则abcd有两种分解方法 a+b+cd 和 ab+cd 解法 可以用递推dp[i] 表示从第i个字符开始的字符串可以有多少种的方案组成用暴力的方法去查找果断是不行的 我们可以用字典树去优化这个算法使得这个查找过程变得又花了好多,然后通过dp得到解
#include <iostream>#include <cstdio>#include <string.h>#include <vector>using namespace std;const int maxn = 4000*100+10;const int maxvlen = 300000+10;const int mod=20071027;char S[maxn],word[4005][105];int len[40005],dp[maxvlen];struct Trie{ int ch[maxn][26]; int val[maxn]; int sz; void clear() {sz=1; memset(ch[0],0,sizeof(ch[0]));} int idx(char c){ return c-‘a‘; } 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_prefixes(char *s, int len, vector<int> &ans) { int u=0; for(int i=0; i<len; ++i) { if(s[i]==‘\n‘) break; int c = idx(s[i]); if(ch[u][c]==0)break; u=ch[u][c]; if(val[u] !=0 ) ans.push_back(val[u]); } }}tree;int main(){ int n,cas=0,L; while(scanf("%s%d",S,&n)==2) { tree.clear(); L = strlen(S); for( int i = 1; i <= n; ++ i ){ scanf("%s",word[i]); len[i]=strlen(word[i]); tree.insert(word[i],i); } memset(dp,0,sizeof(dp)); dp[L]=1; for(int i=L-1; i>=0; --i) { vector<int> E; tree.find_prefixes(S+i,L-i,E); for(int k=0; k<E.size() ; ++k) { int d = E[k]; dp[i]=(dp[i]+dp[ i + len[ d ] ])%mod; } } printf("Case %d: %d\n", ++cas, dp[0]); } return 0;}
的
Trie
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。