AC Automaton (C++ implementation)

gistfile1.cpp

#include <iostream>
#include <map>

using namespace std;

namespace Mygod
{
    class ACAutomaton
    {
        private:
            class Node
            {
                private:
                    char key;
                    Node *parent;
                    map<char, Node*> children;
                    inline Node* child(const char key)
                    {
                        map<char, Node*>::iterator iterator = children.find(key);
                        return iterator == children.end() ? NULL : iterator->second;
                    }
                public:
                    Node *failPtr;
                    int count;
                    #ifndef COUNT_ONLY
                    int depth;
                    #endif
                    Node(const char k = '\0', Node *p = NULL) : key(k), parent(p)
                    {
                        count = 0;
                        #ifndef COUNT_ONLY
                        depth = p ? p->depth + 1 : 0;
                        #endif
                    }
                    inline Node* buildChild(char key)
                    {
                        map<char, Node*>::iterator iterator = children.find(key);
                        return iterator == children.end() ? children[key] = new Node(key, this) : iterator->second;
                    }
                    void buildFailPtr(Node *root)
                    {
                        failPtr = root;
                        if (parent && parent != root)
                        {
                            Node *ptr = parent->failPtr, *temp;
                            while (!(temp = ptr->child(key)))
                                if (ptr == root) break;
                                else ptr = ptr->failPtr;
                            if (temp)
                            #ifdef COUNT_ONLY
                                count += (failPtr = temp)->count;
                            #else
                                failPtr = temp;
                            #endif
                        }
                        for (map<char, Node*>::iterator i = children.begin(); i != children.end(); i++)
                            i->second->buildFailPtr(root);
                    }
                    Node* travel(char key, Node *root)
                    {
                        Node *ptr = this, *temp;
                        while (!(temp = ptr->child(key)))
                            if (ptr == root) return root;
                            else ptr = ptr->failPtr;
                        return temp;
                    }
                    static void remove(Node *&ptr)
                    {
                        for (map<char, Node*>::iterator i = ptr->children.begin(); i != ptr->children.end(); i++)
                            remove(i->second);
                        Node *temp = ptr;
                        ptr = NULL;
                        delete temp; 
                    }
            };
            Node *root;
        public:
            ACAutomaton(const int count, const string iterator())
            {
                root = new Node();
                for (int i = 0; i < count; i++)
                {
                    string pattern = iterator();
                    Node *ptr = root;
                    for (string::iterator j = pattern.begin(); j != pattern.end(); j++) ptr = ptr->buildChild(*j);
                    ptr->count++;
                }
                root->buildFailPtr(root);
            }
            ~ACAutomaton()
            {
                Node::remove(root);
            }
            #ifdef COUNT_ONLY
            int getMatchCount(const string text)
            {
                Node *ptr = root;
                int result = root->count;
                for (string::const_iterator i = text.begin(); i != text.end(); i++)
                    result += (ptr = ptr->travel(*i, root))->count;
                return result;
            }
            #else
            void getMatches(const string text, void handler(int, int, int))
            {
                Node *ptr = root;
                if (root->count) handler(0, 0, root->count);
                int index = 1;
                for (string::const_iterator i = text.begin(); i != text.end(); i++, index++)
                {
                    Node *temp = ptr = ptr->travel(*i, root);
                    do if (temp->count) handler(index - temp->depth, index, temp->count);
                    while (temp != root && (temp = temp->failPtr));
                }
            }
            #endif
    };
}

inline const string cinPatterns()
{
    string result;
    getline(cin, result);
    return result;
}

inline void coutIndex(int startIndex, int endIndex, int count)
{
    cout << '[' << startIndex << ", " << endIndex << ") matched " << count << " time(s)." << endl;
}

int main()
{
    int count;
    cout << "Number of patterns: ";
    cin >> count;
    cinPatterns();    // skip a line
    cout << "Enter the patterns:" << endl;
    Mygod::ACAutomaton automaton(count, cinPatterns);
    cout << "Enter the texts:" << endl;
    string temp;
    while (getline(cin, temp))
    #ifdef COUNT_ONLY
        cout << automaton.getMatchCount(temp) << endl;
    #else
        automaton.getMatches(temp, coutIndex);
    #endif
    return 0;
}