uvaliva3942(trie树)

题目连接:https://vjudge.net/problem/UVALive-3942

trie树

dp[i]=sum(dp[i+len(x)]%mod;

dp[i]表示从字符i开始的字符串的分解方案方案数,x是s[i……L]的前缀

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxnode=500010;
 4 const int sigma=26;
 5 const int N=300010;
 6 const int mod=20071027;
 7 int ch[maxnode][sigma];
 8 int val[maxnode];
 9 int sz;
10 inline int id(char c) {return c-‘a‘;}
11
12 void trie_init()
13 {
14     sz=1;
15     memset(ch[0],0,sizeof(ch[0]));
16 }
17
18 void inser(char *s,int v)
19 {
20     int u=0;
21     for(int i=0;s[i];i++)
22     {
23         int c=id(s[i]);
24         if(!ch[u][c])
25         {
26             memset(ch[sz],0,sizeof(ch[sz]));
27             val[sz]=0;
28             ch[u][c]=sz++;
29         }
30         u=ch[u][c];
31     }
32     val[u]=v;
33 }
34 int num,dp[N],st;
35 void query(char *s)
36 {
37     int u=0;
38     for(int i=0;s[i];i++)
39     {
40         int c=id(s[i]);
41         if(ch[u][c])
42         {
43             u=ch[u][c];
44             if(val[u]) num=(num+dp[st+i+1])%mod;  //
45         }
46         else return;
47     }
48 }
49 int main()
50 {
51     char s[N],p[110];
52     int k=0;
53     while(scanf("%s",s)!=EOF)
54     {
55         trie_init();
56         int m;
57         scanf("%d",&m);
58         while(m--)
59         {
60             scanf("%s",p);
61             inser(p,1);
62         }
63         int len=strlen(s);
64         dp[len]=1;
65         for(int i=len-1;i>=0;i--)
66         {
67             num=0;
68             st=i;
69             query(&s[i]);
70             dp[i]=num;
71         }
72         printf("Case %d: %d\n",++k,dp[0]);
73     }
74     return 0;
75 }

lrj:

 1 // LA3942 Remember the Word
 2 // Rujia Liu
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6
 7 const int maxnode = 4000 * 100 + 10;
 8 const int sigma_size = 26;
 9
10 // 字母表为全体小写字母的Trie
11 struct Trie {
12   int ch[maxnode][sigma_size];
13   int val[maxnode];
14   int sz; // 结点总数
15   void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } // 初始时只有一个根结点
16   int idx(char c) { return c - ‘a‘; } // 字符c的编号
17
18   // 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
19   void insert(const char *s, int v) {
20     int u = 0, n = strlen(s);
21     for(int i = 0; i < n; i++) {
22       int c = idx(s[i]);
23       if(!ch[u][c]) { // 结点不存在
24         memset(ch[sz], 0, sizeof(ch[sz]));
25         val[sz] = 0;  // 中间结点的附加信息为0
26         ch[u][c] = sz++; // 新建结点
27       }
28       u = ch[u][c]; // 往下走
29     }
30     val[u] = v; // 字符串的最后一个字符的附加信息为v
31   }
32
33   // 找字符串s的长度不超过len的前缀
34   void find_prefixes(const char *s, int len, vector<int>& ans) {
35     int u = 0;
36     for(int i = 0; i < len; i++) {
37       if(s[i] == ‘\0‘) break;
38       int c = idx(s[i]);
39       if(!ch[u][c]) break;
40       u = ch[u][c];
41       if(val[u] != 0) ans.push_back(val[u]); // 找到一个前缀
42     }
43   }
44 };
45
46 #include<cstdio>
47 const int maxl = 300000 + 10; // 文本串最大长度
48 const int maxw = 4000 + 10;   // 单词最大个数
49 const int maxwl = 100 + 10;   // 每个单词最大长度
50 const int MOD = 20071027;
51
52 int d[maxl], len[maxw], S;
53 char text[maxl], word[maxwl];
54 Trie trie;
55
56 int main() {
57   int kase = 1;
58   while(scanf("%s%d", text, &S) == 2) {
59     trie.clear();
60     for(int i = 1; i <= S; i++) {
61       scanf("%s", word);
62       len[i] = strlen(word);
63       trie.insert(word, i);
64     }
65     memset(d, 0, sizeof(d));
66     int L = strlen(text);
67     d[L] = 1;
68     for(int i = L-1; i >= 0; i--) {
69       vector<int> p;
70       trie.find_prefixes(text+i, L-i, p);
71       for(int j = 0; j < p.size(); j++)
72         d[i] = (d[i] + d[i+len[p[j]]]) % MOD;
73     }
74     printf("Case %d: %d\n", kase++, d[0]);
75   }
76   return 0;
77 }

时间: 04-19

uvaliva3942(trie树)的相关文章

poj3630 Phone List (trie树模板题)

Phone List Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 26328   Accepted: 7938 Description Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogu

跳跃表,字典树(单词查找树,Trie树),后缀树,KMP算法,AC 自动机相关算法原理详细汇总

第一部分:跳跃表 本文将总结一种数据结构:跳跃表.前半部分跳跃表性质和操作的介绍直接摘自<让算法的效率跳起来--浅谈"跳跃表"的相关操作及其应用>上海市华东师范大学第二附属中学 魏冉.之后将附上跳跃表的源代码,以及本人对其的了解.难免有错误之处,希望指正,共同进步.谢谢. 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类

Trie树学习2

数组实现的Trie树 字符容量有限,可以使用链表实现更为大容量的Trie #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #

trie树(字典树)

1. trie树,又名字典树,顾名思义,它是可以用来作字符串查找的数据结构,它的查找效率比散列表还要高. trie树的建树: 比如有字符串"ab" ,"adb","adc"   可以建立字典树如图: 树的根节点head不存储信息,它有26个next指针,分别对应着字符a,b,c等.插入字符串ab时,next['a'-'a']即next[0]为空,这是申请一个结点放在next[0]的位置,插入字符串db时,next['d'-'a']即next[3]

Trie树

Trie树,即字典树或单词查找树,主要用于大量字符串的检索.去重.排序等操作. 主要原理就是利用字符串的公共前缀建立一棵多叉树,牺牲空间换取时间. 1 //Trie树 2 #include <iostream> 3 #include <string> 4 using std::cin; 5 using std::cout; 6 using std::endl; 7 using std::string; 8 9 const int SIZE = 26; 10 const char B

bzoj4103异或运算 可持久化trie树

要去清华冬令营了,没找到2016年的题,就先坐一坐15年的. 因为n很小,就按照b串建可持久化trie树,a串暴力枚举. 其他的直接看代码. #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { int x=0,f=1,ch=getchar(); while(ch<'0'||ch

hihoCoder 1014 Trie树

#1014 : Trie树 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进. 这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?” 身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字

HDU 1251 Trie树模板题

1.HDU 1251 统计难题  Trie树模板题,或者map 2.总结:用C++过了,G++就爆内存.. 题意:查找给定前缀的单词数量. #include<iostream> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #include<cstdio> #define max(a,b) a>b?a:b #define F(i,a,b

hiho一下 第二周&amp;第四周:从Trie树到Trie图

hihocoder #1014 题目地址:http://hihocoder.com/problemset/problem/1014 hihocoder #1036 题目地址: http://hihocoder.com/problemset/problem/1036 trie图其实就是trie树+KMP #1014trie树 #include<stdio.h> #include <algorithm> #include <cstring> #include <str