Russ Cox's linear search algorithm

linear_search.go

package main

import (
	"fmt"
)

// Uses Russ Cox's linear search algorithm.
func match(name, pattern string) bool {
	p := 0
	n := 0
	nextP := 0
	nextN := 0

	// Would always match.
	if pattern == "*" {
		return true
	}

	for n < len(name) || p < len(pattern) {
		if p < len(pattern) {
			c := pattern[p]

			switch c {
			case '?':
				if n < len(name) {
					p++
					n++
					continue
				}
			case '*':
				nextP = p
				nextN = n + 1
				p++
				continue
			default:
				if n < len(name) && name[n] == c {
					p++
					n++
					continue
				}
			}
		}

		// Restart.
		if 0 < nextN && nextN <= len(name) {
			p = nextP
			n = nextN
			continue
		}
		return false
	}
	return true
}

func main() {
	var examples = []struct {
		s string
		p string
	}{
		{"abcdef", "*"},
		{"abcdef", "*abc"},
		{"abcdef", "*bc???"},
		{"abcdef", "abc*"},
		{"abcdef", "ab*ef"},
		{"abcdef", "ab?def"},
		{"abcdef", "?b?d*"},
	}

	for _, v := range examples {
		fmt.Printf("%s: %v\n", v.s, match(v.s, v.p))
	}
}