Java教程

Trie 板子

本文主要是介绍Trie 板子,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;
const int root=0;    // 默认 Trie 根节点位置为 0
/* trie[i][j] i 记录当前节点位置, 同样只关注指向下一个节点的相对位置, j 是表征当前节点下一个字母的指针
   合起来是当前节点为 i 下一个字母对应编码为 j 的下一个节点的位置为 trie[i][j]
   当前树只存储 26 位小写字母构成的string
*/
int trie[N][26];  // 存储 Trie
int sz=0;   // Trie 大小
int val[N]; // Trie 节点信息

void init(){
    sz=1;
    memset(trie,0,sizeof(trie));
    memset(val,0,sizeof(val));
}

// 将字符串插入 Trie
void insert_str(const string str){
    int ch,pos=root;
    for(int i=0;i<str.size();i++){
        ch=str[i]-'a';
        if(!trie[pos][ch]) trie[pos][ch]=++sz;
        pos=trie[pos][ch];
    }
    val[pos]=1;
    /* val[pos] 的更新
       可以放到 for 循环内,也可以放到 for 循环外面,根据不同的题有不同的方法.
       当在 for 循环内部时,用来表示的含义时 相同的前缀出现的次数.
       当在外面的时候给 val 变成 1 或 -1 表示这个串到这里结束。
    */
}

// 查询字符串 str 是否出现过
bool query_str(const string str){
    int ch,pos=root;
    for(int i=0;i<str.size();i++){
        ch=str[i]-'a';
        if(!trie[pos][ch]) return false;
        pos=trie[pos][ch];
    }
    return val[pos];
}

int main()
{
    ios::sync_with_stdio(0);
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    // ======================================================================
    int n,q;
    string tmp;
    init();
    cin>>n>>q;
    while(n--){
        cin>>tmp; insert_str(tmp);
    }
    while(q--){
        cin>>tmp;
        if(query_str(tmp)) puts("Existed!");
        else puts("Not yet!");
    }

    // ======================================================================
end:
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;
}
/*
输入:
7 2
dgsdbc
zfhdfaaa
absfs
xbcc
vbgdch
syqwq
fgwctc
syqwq
fgwsyq

输出:
Existed!
Not yet!


*/

这篇关于Trie 板子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!