tire树

结构体tire树

例题：洛谷P8306

struct Tire {
    // 小写字母：26， 二进制：2 ... 具体由题
    static const int ALPHABET = 26;
    struct Node {
        int len;
        int cnt; // cnt的定义具体由题，在这是前缀数量
        std::array<int, ALPHABET> next;
        Node() : cnt{}, next{} {}
    };

    std::vector<Node> tr;

    Tire() {
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].len = -1;
        tr[0].next.fill(1);
    }

    int newNode() {
        tr.emplace_back();
        return tr.size() - 1;
    }

    int add(const std::vector<int>& a) {
        int p = 1;
        for (auto x : a) {
            if (!tr[p].next[x]) {
                tr[p].next[x] = newNode();
                tr[tr[p].next[x]].len = tr[p].len + 1;
            }
            p = tr[p].next[x];
            tr[p].cnt ++ ;
        }
        return p;
    }

    int add(const std::string& s, char offset = 'a') {
        std::vector<int> a(s.size());
        for (int i = 0; i < (int)s.size(); i++) {
            a[i] = s[i] - offset;
        }
        return add(a);
    }

    int add(const int x) {
        // 如果是int就是31, LL是62
        std::vector<int> a(31);
        for (int i = 30; i >= 0; i--) {
            a[30 - i] = (x >> i & 1);
        }
        return add(a);
    }

    int next(int p, int x) {
        return tr[p].next[x];
    }

    int next(int p, char c, char offset = 'a') {
        return next(p, c - offset);
    }

    int len(int p) {
        return tr[p].len;
    }

    int size() {
        return tr.size();
    }

    // query写下面

};

字符串-trie树

统计字符串数量

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

void add_s() {
	int p = 0;
	for (int i = 0; i < str.size(); i++) {
		int u = str[i] - 'a';
		if (!ma[p][u]) {
			ma[p][u] = ++ idx;
		} 
		p = ma[p][u];
	}

	cnt[p] ++ ;
}

int find_s() {
	int p = 0;
	for (int i = 0; i < str.size(); i++) {
		int u = str[i] - 'a';
		if (!ma[p][u]) {
			return 0;
		}
		p = ma[p][u];
	}

	return cnt[p];
}

01-tire树

const int N = 1e5 + 10, M = 31 * N;
int ma[M][2], a[N], idx;

void add_s(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		int u = x >> i & 1;
		if (!ma[p][u]) {
			ma[p][u] = ++ idx;
		}
		p = ma[p][u];
	}

}