Trie代码学习

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

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

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

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

 #include <bits/stdc++.h>

 using namespace std;

 #define mst(s,v) memset(s, v, sizeof(s));

 const int maxnode = ;

 const int sigma_size = ;

 //字母表为全体小写字母的Trie

 struct Trie{

     int ch[maxnode][sigma_size];

     int val[maxnode];

     int sz;   //结点总数

     Trie(){ sz=; mst(ch[], ); mst(val, ); }   //初始时只有一个根节点

     int idx(char c) { return c-'a'; }

     //插入字符串s，附加信息为v。v!=0(0代表本身不是单词结点)

     void insert(char *s, int v){

         int u = , n = strlen(s);

         for(int i=; i<n; i++){

             int c = idx(s[i]);

             if(!ch[u][c]){  //结点不存在

                 memset(ch[sz], , sizeof(ch[sz]));

                 val[sz] = ;         //中间结点的附加信息为0

                 ch[u][c] = sz++;

             }

             u = ch[u][c];

         }

         val[u] = v;   //字符串的最后一个字符的附加信息

         //标记在末结点，查询整个单词时有用

     }

     bool find(char *s){

         int u = , len = strlen(s);

         for(int i=; i<len; i++){

             int c = idx(s[i]);

             if(!ch[u][c])  return false;

             u = ch[u][c];

         }

         return true;  //查询整个单词时 return val[u]

     }

 }tree;

 int main(){

     freopen("in.txt", "r", stdin);

     int n, m;

     cin >> n >> m;

     char tmp[];

     for(int i=; i<n; i++){

         cin >> tmp;

         cout << tmp << endl;

         tree.insert(tmp, );

     }

     for(int i=; i<m; i++){

         cin >> tmp;

         cout << endl << tmp << endl;

         if(tree.find(tmp)) cout << "Y" << endl;

         else cout << "N" << endl;

     }

     return ;

 }

 /*

 6 2

 shex

 shexy

 yasherhs

 say

 shrxy

 sher

 yasherhs

 she

 */

2、Trie查询前缀个数

 #include <bits/stdc++.h>

 using namespace std;

 #define mst(s,v) memset(s, v, sizeof(s));

 const int maxnode = ;

 const int sigma_size = ;

 //可以查找前缀，也可以查找单词(map)

 struct Trie{

     int ch[maxnode][sigma_size];

     int sum[maxnode];

     int sz;   //结点总数

     Trie(){ sz=; mst(ch[], ); mst(sum, ); }

     int idx(char c) { return c-'a'; }

     //插入字符串s，附加信息为v。v!=0(0代表本身不是单词结点)

     void insert(char *s){

         int u = , n = strlen(s);

         for(int i=; i<n; i++){

             int c = idx(s[i]);

             if(!ch[u][c]){  //结点不存在

                 memset(ch[sz], , sizeof(ch[sz]));

                 ch[u][c] = sz++;

             }

             sum[ch[u][c]]++;

             u = ch[u][c];

         }

     }

     int find(char *s){

         int u = , len = strlen(s);

         for(int i=; i<len; i++){

             int c = idx(s[i]);

             if(!ch[u][c])  return ;

             u = ch[u][c];

         }

         return sum[u];

     }

 }tree;

 int main(){

     freopen("in.txt", "r", stdin);

     int n, m;

     cin >> n >> m;

     char tmp[];

     for(int i=; i<n; i++){

         cin >> tmp;

         tree.insert(tmp);

     }

     for(int i=; i<m; i++){

         cin >> tmp;

         cout << tmp << endl;

         cout << tree.find(tmp) << endl;

     }

     return ;

 }

3、用指针理解Trie

#include <bits/stdc++.h>

using namespace std;

#define mst(s,v) memset(s, v, sizeof(s));

const int sigma_size = ;

struct node{

    int count;

    node * next[];

}*root;

int idx(char c){ return c-'a'; }

node* build(){

    node* k = new(node);

    k->count = ;

    mst(k->next , );

    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 ;

        word++;

    }

    return r->count;

}

int main(){

    freopen("in.txt", "r", stdin);

    int n, m;

    cin >> n >> m;

    char tmp[];

    root = build();

    for(int i=; i<n; i++){

        cin >> tmp;

        insert(tmp);

    }

    for(int i=; i<m; i++){

        cin >> tmp;

        cout << tmp << endl;

        cout << find(tmp) << endl;

    }

    return ;

}

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开始。

 #include <bits/stdc++.h>

 using namespace std;

 #define mst(s,v) memset(s, v, sizeof(s));

 const int maxnode = ;

 const int sigma_size = ;

 const int maxlen = 1e6 + 5e4;

 int dp[maxlen];

 struct Trie{

     int ch[maxnode][sigma_size];

     int val[maxlen];

     int sz;

     Trie(){ sz=; }

     inline int idx(char c) { return c-'a'; }

     inline void insert(char *s){

         int u = , n = strlen(s);

         for(int i=; i<n; i++){

             int c = idx(s[i]);

             if(!ch[u][c]){

                 ch[u][c] = sz++;

             }

             u = ch[u][c];

         }

         val[u] = ;    //标记单词

     }

     inline int find(char *s, int v){

         int u = , len = strlen(s), ans = ;

         dp[] = v;    //标记能够被识别的前缀位置

         for(int i=; i<len; i++){

             if(dp[i] == v){

                 u = ;

                 for(int j=i+; j<len; j++){

                     int c = idx(s[j]);

                     if(!ch[u][c])  break;

                     //cout<<"u = "<<u<<"    v = "<<v<<"   s[j] = "<<s[j]<<endl;

                     u = ch[u][c];

                     if(val[u]){   //找到单词的前缀

                         ans = max(ans, j);

                         dp[j] = v;    //标记位置

                     }

                 }

             }

         }

         return ans;

     }

 }tree;

 char tmp[maxlen];

 int main(){

 //    freopen("in.txt", "r", stdin);

     int n, m;

     scanf("%d%d", &n, &m);

     for(int i=; i<n; i++){

         scanf("%s", tmp);

         tree.insert(tmp);

     }

     for(int i=; i<=m; i++){

         scanf("%s", tmp+);

         printf("%d\n", tree.find(tmp, i));

     }

     return ;

 }

巴特西

Trie代码学习

最新文章

热门文章