NFA matcher

nfa.cpp

#include <boost/foreach.hpp>
#include <cassert>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

static bool pattern_matches_file(string const& pattern, string const& file) {
    // Build an NFA recognizer (currently only supports '*' and '?')
    static const char ANY = CHAR_MIN;
    map<int, vector<pair<char, int> > > nfa;
    
    int current_state = 0;
    int last_state = 0;
    BOOST_FOREACH(char c, pattern) {
        switch (c) {
        case '?':
            nfa[current_state].push_back(make_pair(ANY, ++last_state));
            current_state = last_state;
            break;
        case '*':
            nfa[current_state].push_back(make_pair(ANY, current_state));
            break;
        default:
            nfa[current_state].push_back(make_pair(c, ++last_state));
            current_state = last_state;
            break;
        }
    }

    const int ACCEPT = current_state;

    // NFA matcher
    set<int> states;
    states.insert(0);

    BOOST_FOREACH(char c, file) {
        set<int> new_states;
        typedef pair<char, int> edge_type;
        BOOST_FOREACH(int s, states) {
            BOOST_FOREACH(edge_type const& edge, nfa[s]) {
                if (edge.first == ANY || edge.first == c)
                    new_states.insert(edge.second);
            }
        }

        states = new_states;
        if (new_states.empty())
            break;
    }

    return states.count(ACCEPT) > 0;
}

int main() {
    assert(pattern_matches_file("foo", "foo"));
    assert(!pattern_matches_file("foo", "bar"));
    assert(pattern_matches_file("f?o", "foo"));
    assert(pattern_matches_file("f*o", "foo"));
    assert(pattern_matches_file("f*o", "floooberdoobervilleinskyo"));
    assert(!pattern_matches_file("f*o", "flooberdoobervilleinsky"));
    return 0;
}