Trie_verify.cpp

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int,int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/01/26  Problem: codechef_NPLFLF / Link: https://www.codechef.com/problems/NPLFLF  ----- */
/* ------問題------

Q個のクエリがある。
1 文字列の追加
2 K個の単語が接尾辞で長さLまで一致しているか
3 i番目に追加した文字列の削除

-----問題ここまで----- */
/* -----解説等-----

接尾辞だが、反転させればこれは接頭辞の共通判定になるのでTrieでできる。
クエリ2は愚直にたどると無理なので、ノードを作成するごとにそのノードのカウントをやっていけばよい。
またK,Lの情報をmapに乗せておくことでクエリに対してlogオーダーで応えることができる。

----解説ここまで---- */

map<PII,int> Map;
// verified https://www.codechef.com/problems/NPLFLF
/*-------Trie Setting---------*/
const int Alphabets = 26;
const int AlphabetBase = 'a'; // '0'
/*------------------------------------*/
class Trie {
	struct node {
		bool isleaf;
		node *children[Alphabets];
		int id;
		int cnt; // 
		node() :cnt(0),isleaf(0), id(nodesize++) { memset(children, 0, sizeof children); }
	} *root;
	static int nodesize;

	static bool is_free_node(node *n) {
		for (int i = 0; i < Alphabets; i++) {
			if (n->children[i] != NULL)return true;
		}
		return false;
	}

	bool _remove(const string& s, node *n, int level) {
		//if(n != NULL){
			if (level == (int)s.size()) {
				return 1;
			}
			else {
				int idx = s[level] - AlphabetBase;
				if (_remove(s, n->children[idx], level + 1)) {
					Map[PII(level+1,n->children[idx]->cnt)]--;
					n->children[idx]->cnt--;
					
					//delete n->children[idx];
					return 1;
					// if(n->cnt==0)delete n->children[idx];
				}
			}
		//}
			return 1;
	}

	static void clean_up(node *n) {
		if (n == 0 || n->isleaf) return;
		for (int i = 0; i < Alphabets; i++) {
			clean_up(n->children[i]);
		}
		delete n;
	}

public:
	Trie() { root = new node(); }
	~Trie() { clean_up(root); }

	int getnodesize() { return nodesize; }
	void insert(string &s) {
		node *n = root;
		for (int level = 0; level < (int)s.size(); level++) {
			int idx = s[level] - AlphabetBase;
			if (n->children[idx] != NULL) {
				n = n->children[idx];
			}
			else {
				n->children[idx] = new node();
				n = n->children[idx];
			}
			n->cnt++;
			Map[PII(level+1,n->cnt)]++;
		}
		n->isleaf = 1;

	}


	bool exists(string &s) {
		node *n = root;
		for (int level = 0; level < (int)s.size(); level++) {
			int idx = s[level] - AlphabetBase;
			if (n->children[idx] == NULL)return 0;
			n = n->children[idx];
		}
		return (n != 0 && n->isleaf); // 
	}
	bool remove(string &s) {
		return _remove(s, root, 0);
	}
};
int Trie::nodesize = 0;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int Q; cin>>Q;
	Trie T;
	
	int q; int L,K,X; vector<string> vs(Q);
	int insertcnt=0;
	VI insr(Q);
	FOR(i,0,Q){
		cin>>q;
		if(q==1){
			cin>>vs[i];
			reverse(ALL(vs[i]));
			T.insert(vs[i]);
			insr[i]++;

		}else if(q==2){
			cin>>K>>L;
			if(Map[PII(L,K)]>0){
				cout<<"YES"<<endl;
			}else {
				cout<<"NO"<<endl;
			}
		}else {
			cin>>X;
			X--;

			if(insr[X]){
				insr[X]--;
				T.remove(vs[X]);
			}
		}
	}

	return 0;
}