pastebin

using namespace std;

const long long INF = 1e18;

const long long N = 2e6 + 20;

 

struct node {

    int nxt[3], cnt, p;

 

    node (int par = -1) {

        p = par;

        nxt[0] = nxt[1] = nxt[2] = 0;

        cnt = 0;

    }

};

 

vector <node> trie(1);

 

int q;

 

void insert(const string &s, int add) {

    int pos = 0;

    for (const char &ch: s) {

        int u = ch - '0';

        if (ch == '#') u = 2;

        if (trie[pos].nxt[u] == 0) {

            trie[pos].nxt[u] = trie.size();

            trie.push_back(node(pos));

        }

 

        pos = trie[pos].nxt[u];

    }

 

    trie[pos].cnt += add; // if there is a vetor -> push once

 

int p[N]; // suffix array

ll sum[N];

 

void build() { // build an automaton-like data structure with no update

    // itterate like bfs

 

    for (int i = 0; i < trie.size(); i ++) sum[i] = trie[i].cnt;

 

    queue <int> vi;

 

    vi.push(0);

    while (vi.size()) {

        int pos = vi.front(); vi.pop();

        for (int u = 0; u <= 2; u ++) if (trie[pos].nxt[u]) {

            int i = trie[pos].nxt[u];

            int j = p[pos];

 

            while (j > 0 && trie[j].nxt[u] == 0)

                j = p[j];

           

            if (pos != 0 && trie[j].nxt[u]) j = trie[j].nxt[u];

            p[i] = j;

           

            sum[i] += sum[j];

            vi.push(i);

        }

    }

 

    // for (int i = 0; i < trie.size(); i ++) {

    //     if (trie[i].nxt[0]) cout << i << ' ' << trie[i].nxt[0] << ' ' << 0 << 'n';

    //     if (trie[i].nxt[1]) cout << i << ' ' << trie[i].nxt[1] << ' ' << 1 << 'n';

    //     if (trie[i].nxt[2]) cout << i << ' ' << trie[i].nxt[2] << ' ' << 2 << 'n';

    // }

 

    // for (int i = 0; i < trie.size(); i ++)

    //     cout << "p[" << i << "]: " << p[i] << 'n';

 

 

ll count(const string &s, ll ans = 0) {

    int pos = 0;

    for (const char &ch: s) {

        int u = ch - '0';

        if (ch == '#') u = 2;

        pos = trie[pos].nxt[u];

        ans += sum[pos];

    }

    return ans;

 

vector <string> save;

 

int main()

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #ifndef ONLINE_JUDGE

        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);

    #endif

 

    cin >> q;

 

    bool built = false;

    for (int i = 1; i <= q; i ++) {

        int op;

        string s;

        cin >> op >> s;    

        if (op == 1) s = '#' + s;    

        insert(s, op == 0);

        if (op) save.push_back(s);

    }

 

    build();

 

    for (const string &s: save) {

        // cout << s << 'n';

        cout << count(s) << 'n';

    }

 

    return 0;

}