acwing算法基础之数据结构--trie算法

1 基础知识

trie树算法，也叫作字典树算法。
用处：用来高效存储和查找字符串集合的数据结构。

（一）
定义变量。

const int N = 1e5 +10;
int son[N][26], cnt[N], idx;
char str[N];

（二）
插入操作。

void insert(char* str) {int p = 0;for (int i = 0; str[i]; ++i) {int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;return;
}

（三）
查询操作。

int query(char* str) {int p = 0;for (int i = 0; str[i]; ++i) {int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

2 模板

const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;
char str[N];void insert(char* str) {int p = 0;for (int i = 0; str[i]; ++i) {int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;return;
}int query(char* str) {int p = 0;for (int i = 0; str[i]; ++i) {int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

3 工程化

class Trie {
public:Trie(int n) {this->n = n;son.resize(n, vector<int>(26, 0));cnt.resize(n, 0);idx = 0; //注意0表示根结点，也表示空结点。}Trie(int n, int m) {this->n = n;this->m = m;son.resize(n, vector<int>(m, 0));cnt.resize(n, 0);idx = 0; //注意0表示根结点，也表示空结点。}void insert(string str) {int p = 0;for (int i = 0; i < str.size(); ++i) {int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;return;}int query(string str) {int p = 0;for (int i = 0; i < str.size(); ++i) {int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];}
private:int n;int m;int idx;vector<vector<int>> son;vector<int> cnt;
};