#include <bits/stdc++.h>
#define DIM 1000001
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
vector < pair <int, char> > G[DIM];
pair <int, int> dp[DIM];
int task, i, nodes = 1, answer, lg;
string s;
void add(int node){
int next_node = -1;
dp[node].second += 1;
if(i == s.size()){
dp[node].first += 1;
return ;
}
for(auto k : G[node])
if(k.second == s[i]){
next_node = k.first;
break;
}
if(next_node < 0){
++nodes;
G[node].push_back(make_pair(nodes, s[i]));
next_node = nodes;
}
++i;
add(next_node);
}
void del(int node){
dp[node].second -= 1;
if(i == s.size()){
dp[node].first -= 1;
return ;
}
int next_node = -1;
for(auto k : G[node])
if(k.second == s[i]){
next_node = k.first;
break;
}
++i;
del(next_node);
}
void frequency(int node){
if(node == -1){
answer = 0;
return ;
}
if(i == s.size()){
answer = dp[node].first;
return ;
}
int next_node = -1;
for(auto k : G[node])
if(k.second == s[i]){
next_node = k.first;
break;
}
++i;
frequency(next_node);
}
void get_prefix(int node){
if(i == s.size()){
lg = i;
return ;
}
if(dp[node].second == 0){
lg = i - 1;
return ;
}
if(node == -1){
lg = 0;
return ;
}
int next_node = -1;
for(auto k : G[node])
if(k.second == s[i]){
next_node = k.first;
break;
}
++i;
get_prefix(next_node);
}
int main(){
while(fin >> task){
fin >> s;
i = 0;
if(task == 0)
add(1);
if(task == 1)
del(1);
if(task == 2){
answer = 1e9;
frequency(1);
fout << answer << "\n";
}
if(task == 3){
answer = 1e9;
lg = 0;
get_prefix(1);
fout << lg << "\n";
}
}
}
Rosu Adrian Andrei AdrianRosu