match.php

<?php

function match($string, $pattern) {
    $automata = new Automata($pattern);
    return $automata->match($string);
}

function get_chars($string) {
    for ($i = 0; $i < strlen($string); $i++) {
        yield $string[$i];
    }
}

class Automata {

    const INITIAL_STATE = 0;

    const NO_MATCH = -1;

    const REPEAT = '*';

    private $states;

    private $accepting;

    public function __construct($pattern) {
        $this->validatePattern($pattern);
        $this->build($pattern);
    }

    public function match($string) {
        $state = self::INITIAL_STATE;
        $chars = get_chars($string);
        foreach ($chars as $char) {
            $state = $this->getNextState($state, $char);
            if ($state == Automata::NO_MATCH) {
                return false;
            }
        }
        return ($state == $this->accepting);
    }

    private function validatePattern($pattern) {
        if (strlen($pattern) > 0 && $pattern[0] == self::REPEAT) {
            throw new Exception("Invalid pattern (repeat char can't appear first)");
        }

        $chars = get_chars($pattern);
        $previousCharIsRepeat = false;
        foreach ($chars as $char) {
            $currentCharIsRepeat = ($char == self::REPEAT);
            if ($currentCharIsRepeat && $previousCharIsRepeat) {
                throw new Exception('Invalid pattern (repeat char appeared twice)');
            }
            $previousCharIsRepeat = $currentCharIsRepeat;
        }
    }

    private function build($pattern) {
        $state = self::INITIAL_STATE;
        $chars = get_chars($pattern);
        $states = array();
        $prevChar = null;
        foreach ($chars as $char) {
            if ($char == self::REPEAT) {
                $key = $this->getKey($state, $prevChar);
                $states[$key] = $state;
            } else {
                $key = $this->getKey($state, $char);
                $states[$key] = ++$state;
            }
            $prevChar = $char;
        }
        $this->states = $states;
        $this->accepting = $state;
    }

    private function getNextState($currentState, $char) {
        $key = $this->getKey($currentState, $char);
        return isset($this->states[$key]) ? $this->states[$key] : self::NO_MATCH;
    }

    private function getKey($state, $char) {
        return "$state $char";
    }

}

assert(match('foo', 'foo'), 'Simple match');
assert(!match('foo', 'bar'), 'Simple mismatch');
assert(!match('hello', 'hell'), 'String too long');
assert(!match('hello', 'helloo'), 'String too short');
assert(match('hello', 'hel*o'), 'Repeat character');
assert(match('helllllo', 'hel*o'), 'Repeat multiple times');
assert(match('helloo', 'hel*o*'), 'Repeat character multiple times');
assert(match('', ''), 'Empty pattern match');
assert(!match('foo', ''), 'Empty pattern mismatch');

try {
    new Automata('*foo');
    assert(false, 'Pattern validation');
} catch (Exception $e) {}

try {
    new Automata('foo**');
    assert(false, 'Pattern validation');
} catch (Exception $e) {}