重庆交易网站建设,网站的后台一般用什么做的,近期重大新闻事件,网站建设行业导航站点目录 1 基础知识2 模板3 工程化 1 基础知识
trie树算法#xff0c;也叫作字典树算法。 用处#xff1a;用来高效存储和查找字符串集合的数据结构。
#xff08;一#xff09; 定义变量。
const int N 1e5 10;
int son[N][26], cnt[N], idx;
char str[N];#xff08;二… 目录 1 基础知识2 模板3 工程化 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, vectorint(26, 0));cnt.resize(n, 0);idx 0; //注意0表示根结点也表示空结点。}Trie(int n, int m) {this-n n;this-m m;son.resize(n, vectorint(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;vectorvectorint son;vectorint cnt;
};
