package main

import (
	"log"
)

func match(pat, s string) bool {
	next := func(i, j int) bool {
		return match(pat[i:], s[j:])
	}
	switch {
	case pat == "":
		return s == ""
	case s == "":
		return pat == ""
	case pat[0] == '\\' && len(pat) > 1:
		return next(2, 1)
	}
	switch pat[0] {
	case '*':
		for i := range s {
			if next(1, i) {
				return true
			}
		}
		return false
	case '?':
		return next(1, 1)
	}
	return pat[0] == s[0] && next(1, 1)
}

func main() {
	type t []struct {
		s        string
		expected bool
	}
	groups := []struct {
		pat   string
		tests t
	}{
		{"", t{
			{"", true},
			{"aa", false},
		}},
		{"aa", t{
			{"aa", true},
			{"", false},
		}},
		{`a\*a\?a`, t{
			{"a*a?a", true},
			{"aaa", false},
		}},
		{`\`, t{
			{"\\", true},
			{"aaa", false},
		}},
		{"a?*bb*cd", t{
			{"aababbcd", true},
			{"abcd", false},
			{"aa?bxcxd", false},
		}},
		{"a*?b*c*d", t{
			{"abcd", false},
			{"aabcd", true},
			{"a?bcd", true},
			{"aa?bxcxd", true},
			{"aa?bxcd", true},
		}},
		{"as*d*?qwe*qwe", t{
			{"as123dssqwe12345678qwe", true},
		}},
	}
	ok := func(got, expect bool) string {
		if got == expect {
			return " ok "
		} else {
			return "fail"
		}
	}
	for _, group := range groups {
		for _, test := range group.tests {
			res := match(group.pat, test.s)
			log.Printf("[%s] %30q ~ %-20q %v",
				ok(res, test.expected), test.s, group.pat, res)
		}
	}
}