数组实现的Trie树 字符容量有限，能够使用链表实现更为大容量的Trie

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <map>

#include <set>

#include <algorithm>

#include <cstdlib>

#include <list>

#include <cmath>

using namespace std;

#define sigma_size 26

#define MAX_LEN 200001

struct trie_node{

	trie_node* next[sigma_size];

	bool is_terminal;

	trie_node(){

		memset(next, 0, sizeof(next));

		is_terminal = false;

	}

};

struct Trie{

	trie_node* root;

	int size;

	int idx(char ch){

		return ch - 'A';

	}

	Trie(){

		root = new trie_node();

		size = 1;

	}

	void Insert(string str){

		trie_node* cur = root;

		int len = str.length();

		for(int i = 0; i < len; i++){

			int ch = idx(str[i]);

			if(cur->next[ch] == NULL){

				cur->next[ch] = new trie_node();

			}

			cur = cur->next[ch];

		}

		cur->is_terminal = true;

                size++;

	}

	bool Query(string str){

		trie_node* cur = root;

		int len = str.length();

		for(int i = 0; i < len; i++){

			int ch = idx(str[i]);

			if(cur->next[ch] == NULL){

				return false;

			}

			else

				cur = cur->next[ch];

		}

		if(cur->is_terminal)

			return true;

		else

			return false;

	}

};