Aho-Corasick

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)

const int NaN = -1;

struct Node{
    int parent, val;
    int child[2] = {};

    int jmp;
    int nxt[2] = {};

    int cnt;

    Node(int parent = NaN, int val = NaN): parent(parent), val(val){
        jmp = 0, cnt = 0;
        FOR(int, i, 0, 1) child[i] = NaN, nxt[i] = 0;
    }
};

struct Aho{
    const int root = 0;
    vector<Node> trie;
    vector<string> str;
    int trieLen = 0;

    bool empty(){
        return trieLen == 0;
    }

    void clear(){
        trie.clear(); trieLen = 0;
        str.clear();
        trie.push_back(Node());
    }

    Aho(){
        clear();
    }

    void addString(const string &s){
        str.push_back(s);
        int node = root;
        for (char c: s){
            c -= '0';
            if (trie[node].child[c] == NaN){
                trie.push_back(Node(node, c)); trieLen++;
                trie[node].child[c] = trieLen;
            }
            node = trie[node].child[c];
        }
        trie[node].cnt++;
    }

    void build(){
        queue<int> q;
        q.push(root);
        while (!q.empty()){
            int node = q.front(); q.pop();
            int par = trie[node].parent;
            int nodeVal = trie[node].val;

            if (par <= 0) trie[node].jmp = 0;
            else {
                int jmp = trie[par].jmp;
                while (jmp > 0 && trie[jmp].child[nodeVal] == NaN)
                    jmp = trie[jmp].jmp;
                if (trie[jmp].child[nodeVal] != NaN)
                    jmp = trie[jmp].child[nodeVal];
                trie[node].jmp = jmp;
            }

            FOR(int, val, 0, 1)
                if (trie[node].child[val] != NaN)
                    trie[node].nxt[val] = trie[node].child[val];
                else
                    trie[node].nxt[val] = trie[trie[node].jmp].nxt[val];

            if (node)
                trie[node].cnt += trie[trie[node].jmp].cnt;

            FOR(int, val, 0, 1) if (trie[node].child[val] != NaN)
                q.push(trie[node].child[val]);
        }
    }

    ll countMatch(const string &s){
        int node = root;
        ll answer = 0;
        for (char c: s){
            c -= '0';
            node = trie[node].nxt[c];
            answer += trie[node].cnt;
        }
        return answer;
    }
};

const int BIT = 20;
Aho corasick[BIT + 1];

void add(const string &s){
    int pos = 0; while (!corasick[pos].empty()) pos++;
    corasick[pos].addString(s);

    FOR(int, i, 0, pos - 1){
        for (string &s: corasick[i].str)
            corasick[pos].addString(s);
        corasick[i].clear();
    }
    corasick[pos].build();
}