//
//  main.cpp
//  Trie
//

#include <iostream>
#include <fstream>
#include <string>
#include <exception>

using namespace std;

#define CHAR_TO_INDEX(x) (x - 'a')
#define INDEX_TO_CHAR(x) (x + 'a')

class ITrie {
public:
    virtual void add(string word) = 0;
    virtual void remove(string word) = 0;
    virtual int occurences(string word) = 0;
    virtual int longestPrefixLength(string word) = 0;
    virtual ~ITrie() { }
};

class Trie : public ITrie {
public:
    
    
    
    void add(string word) {
        auto current = &root;
        
        for (int i = 0; i < (int)word.length(); i++) {
            auto pNext = &(current->nodes[CHAR_TO_INDEX(word[i])]);
            if(*pNext == nullptr) {
                *pNext = new Node(current);
                current->allocs += 1;
            }
            current = *pNext;
        }
        
        current->count += 1;
    }
    
    
    
    void remove(string word) {
        auto current = &root;
        
        bool found = true;
        for (int i = 0; i < (int)word.length(); i++) {
            auto next = current->nodes[CHAR_TO_INDEX(word[i])];
            if(next == nullptr) {
                found = false;
                break;
            }
            current = next;
        }
        
        if(!found) {
            return;
        }
        
        // delete nodes from trie
        current->count -= 1;
        for (int i = (int)word.length() - 1; i >= 0; i--) {
            if((current->count != 0) || (current->allocs != 0) || (current == nullptr)) {
                break;
            }
            
            auto prev = current->parent;
            if(prev != nullptr) {
                delete current;
                prev->allocs -= 1;
                prev->nodes[CHAR_TO_INDEX(word[i])] = nullptr;
            }
            
            current = prev;
        }
    }
    
    
    
    
    int occurences(string word) {
        auto current = &root;
        bool found = true;
        for (int i = 0; i < (int)word.length(); i++) {
            auto next = current->nodes[CHAR_TO_INDEX(word[i])];
            if(next == nullptr) {
                found = false;
                break;
            }
            current = next;
        }
        
        return found ? current->count : 0;
    }
    
    
    
    int longestPrefixLength(string word) {
        auto current = &root;
        
        int len = 0;
        for (int i = 0; i < word.length(); i++) {
            auto next = current->nodes[CHAR_TO_INDEX(word[i])];
            if(next == nullptr) {
                break;
            }
            len += 1;
            current = next;
        }
        
        return len;
    }
    
    ~Trie() {
        
    }
    
private:
    struct Node {
        int count = 0;
        int allocs = 0;
        Node* nodes[26] = { nullptr };
        Node* parent = nullptr;
        
        Node(Node* parent) {
            this->parent = parent;
        }
    };
    
    Node root = Node(nullptr);
};

int main(int argc, const char * argv[]) {
    ifstream in("trie.in");
    ofstream out("trie.out");
    
    ITrie* t = new Trie();
    
    int op; string word;
    while((in >> op >> word))
    {
        switch (op) {
            case 0:
                t->add(word);
                break;
            case 1:
                t->remove(word);
                break;
            case 2:
                out << t->occurences(word) << '\n';
                break;
            case 3:
                out << t->longestPrefixLength(word) << '\n';
                break;
            default:
                break;
        }
    }
    
    delete t;
    return 0;
}