#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>
using namespace std;

//this source scores 70p because of 'time limit exceeded'
//the official source does not have pointer deletion and is thus faster

struct Trie
{
    char val;
    int num=0;
    unordered_map<char, Trie*> children;
};

void Insert(Trie* root, string s)
{
    Trie* p=root;
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])==p->children.end())
        {
            Trie* node=new Trie;
            node->val=s[i];
            p->children[s[i]]=node;
        }
        p=p->children[s[i]];
    }
    p->num++;
}


void Delete(Trie* root, string s)
{
    Trie* p=root, *last=root;
    int last_index=-1;
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])==p->children.end())//no such child found
            return;
        p=p->children[s[i]];
        if (p->children.size()>1 || (i!=s.size()-1 && p->num))//put 'last' to longest common prefix
            last=p, last_index=i;
    }
    p->num--;
    if (p->num)
        return;
    if (p->children.size()) //s is a prefix of some word
        return;
    last_index++;
    Trie* i=last->children[s[last_index]], *nxt;
    last->children.erase(s[last_index]);
    while (last_index<s.size())
    {
        //cout<<'\t'<<"deleted "<<i->val<<'\n';
        if (last_index==s.size()-1)
            delete i;
        else
        {
            nxt=i->children[s[last_index+1]];
            delete i;
            i=nxt;
        }
        last_index++;
    }
}

int Find(Trie* root, string s)
{
    Trie* p=root;
    //cout<<" -- ";
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])!=p->children.end())
        {
            p=p->children[s[i]];
            //cout<<s[i];
        }
        else
        {
            //cout<<" no such char: "<<s[i]<<' ';
            return 0;

        }

    }
    return p->num;
}

int LongestPrefix(Trie* root, string s)
{
    //cout<<"Find longest prefix of "<<s<<" in Trie \n";
    int Max=0;
    Trie* p=root;
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])!=p->children.end())
        {
            Max=i+1;
            p=p->children[s[i]];
        }
        else
            return Max;
    }
    return Max;
}

int main()
{
    ifstream f("trie.in");
    int a;
    string s;
    Trie* root=new Trie;
    ofstream g("trie.out");
    while (f>>a)
    {
        f>>s;
        if (a==0)
            Insert(root, s);
        if (a==1)
            Delete(root, s);
        if (a==2)
            g<<Find(root, s);
        if (a==3)
            g<<LongestPrefix(root, s);

    }
}