#include <bits/stdc++.h>
# include <iostream>
# include <map>
# include <vector>
# include <string>
# include <queue>

#include <unordered_map>

#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>

using namespace std;

template <typename T>
class BorNode
{

public:
    typedef T value_type;
    std::unordered_map<value_type, BorNode*> links;
    BorNode *fail, *term;  // Предыдущее состояние для функции отката. Только для root равно NULL.
    //BorNode *term; // Ближайшее терминальное состояние. Если отстутствует - NULL
    bool out;

public:
    BorNode(BorNode *fail_node = NULL)
            : fail(fail_node)
            , term(NULL)
            , out(false)
    { }

    BorNode* getLink(const char& c) const
    {
        auto iter = links.find(c);
        if (iter != links.cend())
        {
            return iter->second;
        }
        else
        {
            return nullptr;
        }
    }

    bool isTerminal() const
    {
        return out;
    }
};


template<typename T, typename Map, typename ResultCont = std::vector<std::vector<T>>>
class AhoCorasick
{
public:
    typedef void (*Callback) (const char* substr);
    typedef BorNode<T> bor_type;
    bor_type root;
    vector<string> words;
    bor_type* current_state;

public:
    template<typename R>
    void insert(const R &range)
    {
        insert(boost::begin(range), boost::end(range));
    }

    template<typename ForwardIterator>
    void insert(ForwardIterator begin, ForwardIterator end)
    {
        words.emplace_back(string());
        words.back().reserve(std::distance(begin, end));

        bor_type *current_node = &root;
        for(auto it = begin; it != end; ++it)
        {
            bor_type *child_node = current_node->getLink(*it);
            if (!child_node)
            {
                child_node = new bor_type(&root);
                current_node->links[*it] = child_node;
            }
            current_node = child_node;
            words.back().push_back(*it);
        }
        current_node->out = true;
        //current_node->out = int(words.size()) - 1;
        //words.push_back(str);
    }

    void init()
    {
        std::queue<bor_type *> q;
        q.push(&root);
        while (!q.empty())
        {
            bor_type *current_node = q.front();
            q.pop();
            for (auto iter = current_node->links.cbegin();
                 iter != current_node->links.cend(); ++iter)
            {
                const T symbol = iter->first;
                bor_type *child = iter->second;

                // Defining .fail for the childnode
                bor_type *temp_node = current_node->fail;
                while (temp_node)
                {
                    bor_type *fail_candidate = temp_node->getLink(symbol);
                    if (fail_candidate)
                    {
                        child->fail = fail_candidate;
                        break;
                    }
                    temp_node = temp_node->fail;
                }

                // Defining .term for the childnode using .term of current node
                if (child->fail->isTerminal())
                {
                    child->term = child->fail;
                }
                else
                {
                    child->term = child->fail->term;
                }
                q.push(child);
            }
        }
    }

    void step(const T& c)
    {
        while (current_state)
        {
            bor_type *candidate = current_state->getLink(c);
            if (candidate)
            {
                current_state = candidate;
                return;
            }
            current_state = current_state->fail;
        }
        current_state = &root;
    }

    void printTermsForCurrentState(Callback callback) const
    {
        if (current_state->isTerminal()) {
            //callback(words[current_state->out].c_str());
        }
        bor_type *temp_node = current_state->term;
        while (temp_node) {
            //callback(words[temp_node->out].c_str());
            temp_node = temp_node->term;
        }
    }

    template <typename ForwardIterator>
    void find(ForwardIterator begin, ForwardIterator end, Callback callback)
    {
        current_state = &root;
        for(auto it = begin; it != end; ++it)
        {
            //cout << *str << ':' << endl;
            step(*it);
            //printTermsForCurrentState(callback);
        }
    }
};

template<typename T, typename Compare = std::less<T>,
         typename Alloc = std::allocator<std::pair<const T, BorNode<T> *>>,
        typename ResultCont = std::vector<std::vector<T>>>
using Aho_Corasik = AhoCorasick<T, std::map<T, BorNode<T> *, Compare, Alloc>, ResultCont>;

template<typename T, typename Hash = std::hash<T>, typename Pred = std::equal_to<T>,
        typename Alloc = std::allocator<std::pair<const T, BorNode<T>*>>,
        typename ResultCont = std::vector<std::vector<T>>>
using Aho_Corasik_Hash = AhoCorasick<T, std::unordered_map<T, BorNode<T>*, Hash, Pred, Alloc>, ResultCont>;


int main( )
{
    Aho_Corasik<char> ac;
    Aho_Corasik_Hash<int> ach;

    return 0;
}