博客

字典树

当题目给你一些可数的不同字符时，就可以联想到这个字典树。

下面是学长给的板子

板子

const int MAXN=1e6+10;
int trei[MAXN][26];
int tot=1;
bool mark[MAXN];
int num[MAXN];


void insert(string a){//将传入的字符存进字典树中
    int root = 0;
    for(int i = 0; i<a.length();i++){
        int id=a[i]-'a';
        if(!trei[root][id]){
            trei[root][id]=tot++;
        }
        root=trei[root][id];//更新根
        num[root]++;//这个字母被访问的次数
    }
    mark[root]=true;
    //将这个字符串的末尾字符作为根标记
}

bool search(string a){//判定传入的字符串是否出现在已存的字典中
    int root = 0;
    for(int i = 0;i< a.length() ;i ++){
        int id=a[i]-'a';
        if(!trei[root][id])return false;
        root = trei[root][id];
    }
    return mark[root];
}

例题

例题一

hdu1251

字典树板子题直接看代码吧

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
const int MAXN=1e6+10;
int trei[MAXN][26];
int tot=1;
bool mark[MAXN];
int num[MAXN];


void insert(string a){
    int root = 0;
    for(int i = 0; i<a.length();i++){
        int id=a[i]-'a';
        if(!trei[root][id]){
            trei[root][id]=tot++;
        }
        root=trei[root][id];
        num[root]++;
    }
    mark[root]=true;
}

int search(string a){
    int root = 0;
    for(int i = 0;i< a.length() ;i ++){
        int id=a[i]-'a';
        if(!trei[root][id])return 0;
        root = trei[root][id];
    }
    return num[root];
}


int main(){
    string a;
    while(getline(cin, a)){
        if(a.length()==0)break;
        insert(a);
    }
    while(cin >> a){
        printf("%d\n", search(a));
    }
    return 0;
}

例题二

hdu2072


这题如果用字典树的话会比较麻烦，主要是因为用set能过字典树就显得比较复杂。

我们首先用sstream里的istringstream来分割字符串为一个个的单词（主要是这题会用多个空格来卡你，所以你直接遍历会比较麻烦），然后存进set里，如果用字典树的话就是存进trie里看是否根已经标记，如果未标记就+1。

这里set能过并且比较简单直接看set的（主要是学习一下sstream）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<sstream>
#include<set>

using namespace std;
const int MAXN=1e5+10;

int main(){
    string a;
    while(getline(cin, a)){
        if(a.length()==1&&a[0]=='#')break;
        istringstream word(a);
        set<string>find;
        string temp;
        while(word >> temp){
            find.insert(temp);
        }
        int cou=0;
        cou=find.size();
        printf("%d\n", cou);
    }
    return 0;
}

例题三

hdu1075


这里的话我们用map存的，因为map可以直接让两个字符串互相关联。

直接康代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<sstream>
#include<map>
#include<set>
using namespace std;
const int MAXN=1e5+10;

map<string, string> mmp;

int main(){
    string temp, fire;
    cin >> temp;
    while(cin >> temp){
        if(temp=="END")break;
        cin >> fire;
        mmp[fire]=temp;
    }
    cin >> temp;
    getchar();
    while(getline(cin, temp)){
        if(temp=="END")break;
        int kong=0;
        int l=temp.length();
        fire="";//相当于把这个字符串清除
        for(int i=0;i<l;i++){
            if(temp[i]>='a'&&temp[i]<='z'){
                fire+=temp[i];
            }else{
                if(mmp[fire]!="")cout << mmp[fire];
                else cout << fire;
                fire="";
                printf("%c", temp[i]);
                //这里因为不是小写字母，所以不会存入fire，并且我们需要打印它
            }
        }
        printf("\n");
    }
    return 0;
}