Tire树

Trie树

用来快速存储和查找字符串集合的数据结构

#include <iostream>
using namespace std;

const int N = 100010;

//idx，当前用到了哪个下标
int son[N][26], cnt[N], idx;

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表示节点创建的先后序号
        //而u就代表这个节点的子节点
		p = son[p][u];
	}
	cnt[p]++;
}

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];
}

int main()
{
	int t;
	cin >> t;
	while(t--){
		string op;
		cin >> op;
		string str;
		if (op == "I") {
			cin >> str;
			insert(str);
		} else {
			cin >> str;
			cout << query(str) << endl;
		}
	}
	return 0;
}

前缀树(左程云版)

https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b?tab=note

#include <bits/stdc++.h>
using namespace std;
#define int long long

// 前缀树
// 有多少个字符串以某一个字符串作为开头
// pass 只要经过就 + 1
// end 以这个字符结束 + 1
// 没有路就新建节点，已经有路了就复用节点

const int N = 1e6 + 10;
// tree[i][j]: 从 i 节点经过 j 到了 tree[i][j] 节点
int tree[N][26];
int e[N];
int p[N];
int cnt = 1;

void insert(string str) {
    // 头节点是 1
    // 每次都从头节点出发
    int pos = 1;
    p[pos]++;
    for (int i = 0; i < str.size(); i++) {
        int path = str[i] - 'a';
        // 如果是 0, 那就说明从 pos 出发走 path 还没有节点
        // 那就新建一个节点
        if (tree[pos][path] == 0) {
            tree[pos][path] = ++cnt;
        }
        // 此时的 pos 就是下一个节点
        pos = tree[pos][path];
        // pos 这个节点经过的次数 + 1
        p[pos]++;
    }
    // 到最后一个位置, 以这个节点结束的位置 + 1
    e[pos]++;
}

int find(string str) {
    int pos = 1;
    for (int i = 0; i < str.size(); i++) {
        int path = str[i] - 'a';
        // 此路不同，那就没找到
        if (tree[pos][path] == 0) {
            return 0;
        }
        pos = tree[pos][path];
    }
    return e[pos];
}

int prefix(string str) {
    int pos = 1;
    for (int i = 0; i < str.size(); i++) {
        int path = str[i] - 'a';
        if (tree[pos][path] == 0) {
            return 0;
        }
        pos = tree[pos][path];
    }
    return p[pos];
}

void erase(string str) {
    if (find(str)) {
        int pos = 1;
        p[pos]--;
        for (int i = 0; i < str.size(); i++) {
            int path = str[i] - 'a';
            // 下一个位置 - 1 之后如果 = 0, 那么剩下的都不用看了 
            if (--p[tree[pos][path]] == 0) {
                // 此路不通
                tree[pos][path] = 0;
                return;
            }
            pos = tree[pos][path];
        }
        e[pos]--;
    }      
}

void clear() {
    for (int i = 1; i <= cnt; i++) {
        memset(tree[i], 0, sizeof tree[i]);
        e[i] = 0;
        p[i] = 0;
    }
    cnt = 1;
}

void solve() {
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int op; cin >> op;
        string str; cin >> str;
        if (op == 1) insert(str);
        else if (op == 2) erase(str);
        else if (op == 3) {
            if (find(str)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        } else {
            cout << prefix(str) << endl;
        }
    }

}   

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}