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

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) //implement
{
    Trie* p=root, *r, *tmp;
    int pi=-1;
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])==p->children.end())
            return;
        p=p->children[s[i]];
        if (p->children.size()>1 || (p->num && i!=s.size()-1))
            r=p, pi=i;
    }
    p->num--;
    if (p->num)
        return;
    if (!(p->children.empty()))
        return; // we do not have to delete the nodes, because it is a prefix to another word
    //cout<<"We can delete from: "<<r->val<<'\n';
    pi++;
    tmp=r;
    r=r->children[s[pi]];
    tmp->children.erase(s[pi]);
    while (pi<s.size())
    {
        if (pi+1==s.size())
            delete r;
        else
        {
            tmp=r;
            r=r->children[s[++pi]];
            delete tmp;
        }
        pi++;
    }

}

int Find(Trie* root, string s)
{
    Trie* p=root;
    for (int i=0;i<s.size();i++)
    {
        if (p->children.find(s[i])!=p->children.end())
        {
            p=p->children[s[i]];
        }
        else
            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("test1.in");
    int a;
    string s;
    Trie* root=new Trie;
    ofstream g("trie.out");
    while (!f.eof())
    {
        f>>a>>s;
        if (f.eof())
            break;
        switch(a)
        {
            case 0:
                {
                    cout<<"Request number "<<a<<": ";
                    Insert(root, s);
                    cout<<"Added "<<s<<'\n';
                    break;
                }
            case 1:
                {
                    cout<<"Request number "<<a<<": ";
                    Delete(root, s);
                    cout<<"Deleted "<<s<<'\n';
                    break;
                }
            case 2:
                {
                    cout<<"Request number "<<a<<": ";
                    g<<Find(root, s)<<'\n';
                    break;
                }
            case 3:
                {
                    cout<<"Request number "<<a<<": ";
                    g<<LongestPrefix(root, s)<<'\n';
                    break;
                }
            default:
                {
                    cout<<"Error";
                    break;
                }
        }
    }
}