#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)

{

    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;

        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<<": ";

                    int res=Find(root, s);

                    g<<res<<'\n';

                    //cout<<res<<'\n';

                    break;

                }

            case 3:

                {

                    //cout<<"Request number "<<a<<": ";

                    int res=LongestPrefix(root, s);

                    g<<res<<'\n';

                    //cout<<res<<'\n';

                    break;

                }

            default:

                {

                    break;

                }

        }

    }

}