首页 > 其他 > 详细

Trie代码学习

时间:2018-08-20 00:08:21      阅读:248      评论:0      收藏:0      [点我收藏+]

感觉不把这个Trie理解一下,自动机的代码看起来有点费劲。

这里代码的学习仿照训练指南209页。

 

这里如果只是查询单词,感觉用map更好,但是如果查前缀,还是用Trie。

1、Trie查询前缀字符串是否存在。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define mst(s,v) memset(s, v, sizeof(s)); 
 4 const int maxnode = 10100;
 5 const int sigma_size = 26;
 6 //字母表为全体小写字母的Trie 
 7 struct Trie{
 8     int ch[maxnode][sigma_size];
 9     int val[maxnode];
10     int sz;   //结点总数 
11     Trie(){ sz=1; mst(ch[0], 0); mst(val, 0); }   //初始时只有一个根节点 
12     int idx(char c) { return c-a; }
13     //插入字符串s,附加信息为v。v!=0(0代表本身不是单词结点) 
14     void insert(char *s, int v){
15         int u = 0, n = strlen(s);
16         for(int i=0; i<n; i++){
17             int c = idx(s[i]);
18             if(!ch[u][c]){  //结点不存在 
19                 memset(ch[sz], 0, sizeof(ch[sz]));
20                 val[sz] = 0;         //中间结点的附加信息为0 
21                 ch[u][c] = sz++;
22             }
23             u = ch[u][c]; 
24         }
25         val[u] = v;   //字符串的最后一个字符的附加信息
26         //标记在末结点,查询整个单词时有用 
27     }
28     bool find(char *s){
29         int u = 0, len = strlen(s);
30         for(int i=0; i<len; i++){
31             int c = idx(s[i]);
32             if(!ch[u][c])  return false;
33             u = ch[u][c];
34         }
35         return true;  //查询整个单词时 return val[u] 
36     }
37 }tree;
38 int main(){
39     freopen("in.txt", "r", stdin);
40     int n, m;
41     cin >> n >> m;
42     char tmp[105];
43     for(int i=0; i<n; i++){
44         cin >> tmp;
45         cout << tmp << endl;
46         tree.insert(tmp, 1);
47     }
48     for(int i=0; i<m; i++){
49         cin >> tmp;
50         cout << endl << tmp << endl;
51         if(tree.find(tmp)) cout << "Y" << endl;
52         else cout << "N" << endl;
53     }
54     return 0;
55 }
56 /*
57 6 2
58 shex 
59 shexy
60 yasherhs
61 say
62 shrxy
63 sher
64 yasherhs
65 she
66 */

 

2、Trie查询前缀个数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define mst(s,v) memset(s, v, sizeof(s)); 
 4 const int maxnode = 10100;
 5 const int sigma_size = 26;
 6 //可以查找前缀,也可以查找单词(map) 
 7 struct Trie{
 8     int ch[maxnode][sigma_size];
 9     int sum[maxnode];
10     int sz;   //结点总数 
11     Trie(){ sz=1; mst(ch[0], 0); mst(sum, 0); }
12     int idx(char c) { return c-a; }
13     //插入字符串s,附加信息为v。v!=0(0代表本身不是单词结点) 
14     void insert(char *s){
15         int u = 0, n = strlen(s);
16         for(int i=0; i<n; i++){
17             int c = idx(s[i]);
18             if(!ch[u][c]){  //结点不存在 
19                 memset(ch[sz], 0, sizeof(ch[sz]));
20                 ch[u][c] = sz++;
21             }
22             sum[ch[u][c]]++;
23             u = ch[u][c]; 
24         }
25     }
26     int find(char *s){
27         int u = 0, len = strlen(s);
28         for(int i=0; i<len; i++){
29             int c = idx(s[i]);
30             if(!ch[u][c])  return 0;
31             u = ch[u][c];
32         }
33         return sum[u];
34     }
35 }tree;
36 int main(){
37     freopen("in.txt", "r", stdin);
38     int n, m;
39     cin >> n >> m;
40     char tmp[105];
41     for(int i=0; i<n; i++){
42         cin >> tmp;
43         tree.insert(tmp);
44     }
45     for(int i=0; i<m; i++){
46         cin >> tmp;
47         cout << tmp << endl;
48         cout << tree.find(tmp) << endl;
49     }
50     return 0;
51 }

 

3、用指针理解Trie

#include <bits/stdc++.h>
using namespace std;
#define mst(s,v) memset(s, v, sizeof(s)); 
const int sigma_size = 26;
struct node{
    int count;
    node * next[26];
}*root;
int idx(char c){ return c-a; }
node* build(){
    node* k = new(node);
    k->count = 0;
    mst(k->next , 0);
    return k;
}
void insert(char* s){
    node* r = root;
    char* word = s;
    while(*word){
        int c = idx(*word);
        if(r->next[c] == NULL) r->next[c] = build();
        r = r->next[c];
        r->count++;
        word++;
    }
}
int find(char* s){
    node* r = root;
    char* word = s;
    while(*word){
        int c = idx(*word);
        r = r->next[c];
        if(r==NULL)  return 0;
        word++;
    }
    return r->count;
}
int main(){
    freopen("in.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    char tmp[105];
    root = build();
    for(int i=0; i<n; i++){
        cin >> tmp;
        insert(tmp);
    }
    for(int i=0; i<m; i++){
        cin >> tmp;
        cout << tmp << endl;
        cout << find(tmp) << endl;
    }
    return 0;
}

 

Trie灵活的地方是在插入时对点的属性的更新,以及查询时与其他算法的结合。

 

 

 

这里将AC自动机summer-work那里的C - L语言拿过来,感受在查询变化的一些思路。

题意:n(1,20)模式串(可以有包含关系(这就决定了不能贪心)),m(1,20)文本串,对每个文本串,n个模式串最多可以组成的最长前缀的位置。

这题就是在find()上思考解法,正解应该是dp[i]是否能理解前i个单词,这里因为是学习Trie,所以就暴力吧(感觉自己太水)。

这里总结一个套路,因为是单词而非前缀,所以insert()时点的属性是val=1。

为了创造vis(是否理解前i个单词)的边界条件vis[0]=v(明显可以识别),所以这里scanf(s+1),即遍历时从i+1开始。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define mst(s,v) memset(s, v, sizeof(s)); 
 4 const int maxnode = 210;
 5 const int sigma_size = 26;
 6 const int maxlen = 1e6 + 5e4;
 7 int dp[maxlen];
 8 struct Trie{
 9     int ch[maxnode][sigma_size];
10     int val[maxlen];
11     int sz;
12     Trie(){ sz=1; }
13     inline int idx(char c) { return c-a; }
14     inline void insert(char *s){
15         int u = 0, n = strlen(s);
16         for(int i=0; i<n; i++){
17             int c = idx(s[i]);
18             if(!ch[u][c]){
19                 ch[u][c] = sz++;
20             }
21             u = ch[u][c]; 
22         }
23         val[u] = 1;    //标记单词 
24     }
25     inline int find(char *s, int v){
26         int u = 0, len = strlen(s), ans = 0;
27         dp[0] = v;    //标记能够被识别的前缀位置
28         for(int i=0; i<len; i++){
29             if(dp[i] == v){
30                 u = 0;
31                 for(int j=i+1; j<len; j++){
32                     int c = idx(s[j]);
33                     if(!ch[u][c])  break;
34                     //cout<<"u = "<<u<<"    v = "<<v<<"   s[j] = "<<s[j]<<endl;
35                     u = ch[u][c];
36                     if(val[u]){   //找到单词的前缀
37                         ans = max(ans, j);
38                         dp[j] = v;    //标记位置 
39                     }
40                 }
41             }    
42         }
43         return ans;
44     }
45 }tree;
46 char tmp[maxlen];
47 int main(){
48 //    freopen("in.txt", "r", stdin);
49     int n, m;
50     scanf("%d%d", &n, &m);
51     for(int i=0; i<n; i++){
52         scanf("%s", tmp);
53         tree.insert(tmp);
54     }
55     for(int i=1; i<=m; i++){
56         scanf("%s", tmp+1);
57         printf("%d\n", tree.find(tmp, i));
58     }
59     return 0;
60 }

 

Trie代码学习

原文:https://www.cnblogs.com/seaupnice/p/9496641.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!