#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <map>

class KeywordTree {
public:
    typedef void(*foundCallback)(int patternNr, int position);

    KeywordTree(const std::vector<std::string>& patterns)
    : root_(new Node(0, '\0'))
    {
        int n = 0;
        for (std::vector<std::string>::const_iterator it = patterns.begin();
             it != patterns.end();
             ++it, ++n) {
            insertPattern(*it, n);
            lengths_[n] = it->length();
        }
        computeLinks();
    }
    ~KeywordTree();
    void findOccurences(const std::string& text, foundCallback cb);
private:
    KeywordTree(const KeywordTree &kwt);
    KeywordTree& operator=(const KeywordTree &rhs);

    void insertPattern(const std::string& pattern, int patterNr);
    void computeLinks();

    struct Node {
        typedef std::map<char, Node *> Childs;
        typedef std::map<char, Node *>::iterator ChildIterator;

        Node(Node *parent, char edgeChar) 
        : parent_(parent)
        , definesPatternNr_(-1)
        , edgeChar_(edgeChar) {};

        bool isLeaf() { return childs_.empty(); };
        bool hasChild(char ch) { return (childs_.find(ch) != childs_.end()); };

        Node *parent_;
        Node *failure_;
        Node *output_;
        int definesPatternNr_;
        char edgeChar_;                  // char of edge pointing to this node
        Childs childs_;
    };

    void freeTree(Node *n);

    Node *root_;
    std::map<int, int> lengths_;
};

KeywordTree::~KeywordTree()
{
    freeTree(root_);
}

void KeywordTree::insertPattern(const std::string& pattern, int patternNr)
{
    Node *n = root_;
    for (std::string::const_iterator it = pattern.begin();
         it != pattern.end();
         ++it) {
        Node::ChildIterator ch = n->childs_.find(*it);
        if (ch != n->childs_.end()) {
            n = ch->second;                          // follow path
        } else {
            n->childs_[*it] = new Node(n, *it);      // create path
            n = n->childs_[*it];
        }
    }
    n->definesPatternNr_ = patternNr;
}

void KeywordTree::computeLinks()
{
    root_->failure_ = root_;
    // set all failure links in depth 1 to root + put all nodes depth 1 in a queue
    std::queue<Node *> qu;
    for (Node::ChildIterator it = root_->childs_.begin();
         it != root_->childs_.end();
         ++it) {
        it->second->failure_ = root_;
        qu.push(it->second);
    }
    // del all nodes depth 1 in queue; put all nodes depth 2 in queue
    for (int i = 0, n = qu.size(); i != n; ++i) {
        Node *n = qu.front();
        qu.pop();
        for (Node::ChildIterator it = n->childs_.begin();
             it != n->childs_.end();
             ++it) {
            qu.push(it->second);
        }
    }
    // compute links for depht >= 2
    while (!qu.empty()) {
        Node *n = qu.front();
        qu.pop();
        char ch = n->edgeChar_;
        Node *m = n->parent_->failure_;
        while (m != root_ && !m->hasChild(ch)) {
            m = m->failure_;
        }
        if (m != root_) {
            n->failure_ = m->childs_[ch];
        } else {
            Node::ChildIterator chit = root_->childs_.find(ch);
            if (chit != root_->childs_.end()) {
                n->failure_ = chit->second;
            } else {
                n->failure_ = root_;
            }
        }
        if (n->failure_->definesPatternNr_ != -1) {
            n->output_ = n->failure_;
        } else {
            n->output_ = n->failure_->output_;
        }
        // enqueue childs
        for (Node::ChildIterator it = n->childs_.begin();
             it != n->childs_.end();
             ++it) {
            qu.push(it->second);
        }
    }
}

void KeywordTree::freeTree(Node *n)
{
    if (n->isLeaf()) {
        delete n;
        return;
    }
    for (Node::ChildIterator ch = n->childs_.begin();
         ch != n->childs_.end();
         ++ch) {
        freeTree(ch->second);
    }
}

void KeywordTree::findOccurences(const std::string& text, foundCallback cb)
{
    Node *n = root_;
    unsigned int i = 0;
    while (i < text.length()) {
        while (n->childs_.find(text[i]) != n->childs_.end()) {
            n = n->childs_[text[i]];
            if (n->definesPatternNr_ != -1) {
                cb(n->definesPatternNr_, i - lengths_[n->definesPatternNr_] + 1);
            }
            if (n->output_ != 0) {
                Node *m = n->output_;
                while (m != 0) {
                    cb(m->definesPatternNr_, i - lengths_[m->definesPatternNr_] + 1);
                    m = m->output_;
                }
            }
            ++i;
        }    
        if (n == root_) {
            ++i;
        } else {
            n = n->failure_;
        }
    }
}

std::vector<std::string> patterns;

void cb(int patternNr, int position)
{
    std::cout << "found " << patterns[patternNr] << " @ " << position << "\n";
}

int main(int argc, char **argv)
{
    for (int i = 2; i < argc; ++i) {
        patterns.push_back(argv[i]);
    }
    
    KeywordTree kwt(patterns);

    char buffer[1024];
    std::ifstream inf(argv[1]);
    for (;;) {
        if (!inf.getline(buffer, sizeof (buffer)))
            break;
        std::cout << buffer << "\n";
        kwt.findOccurences(buffer, cb);
    }
}