sub-matrix.go

package main

import (
	"bufio"
	"fmt"
	"io"
	"strconv"
	"strings"
)

var input = `10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
4 6
123412
561212
123634
781288
2 2
12
34
`

func main() {
	var mxs [2]Matrix
	rdr := bufio.NewReader(strings.NewReader(input))

	for i := 0; ; i++ {

		m, err := CreateMatrix(rdr)
		if err != nil {
			return
		}

		idx := i % 2
		mxs[idx] = m

		if idx == 1 {
			// both matrices were created
			if mxs[0].Has(mxs[1]) {
				fmt.Println("YES")
			} else {
				fmt.Println("NO")
			}

		}

	}
}

func createEmptyMatrix(dx, dy int) Matrix {
	m := make([][]byte, dy)
	for i := 0; i < dy; i++ {
		m[i] = make([]byte, dx)
	}
	return m
}

func CreateMatrix(rdr *bufio.Reader) (Matrix, error) {
	dx, dy, err := parseDimensions(rdr)
	if err != nil {
		return nil, err
	}

	m := createEmptyMatrix(dx, dy)

	for i := 0; i < dy; i++ {
		for j := 0; j < dx; j++ {
		RETRY:
			if r, sz, err := rdr.ReadRune(); err != nil {
				return m, io.EOF
			} else {
				if sz > 1 || r == '\n' || r == '\r' {
					// fmt.Printf("Skipping %q\n", string(r))
					goto RETRY
				}
				// fmt.Printf("Read [%d,%d]: %s\n", i, j, string(r))
				m[i][j] = byte(r - '0')
			}
		}
	}

	return m, nil
}

type Point struct {
	x, y int
}

func m2v(m Matrix, p Point, dx, dy int) []byte {
	res := make([]byte, 0, dx*dy) // Allocate flat vector
	for _, v := range m[p.x : p.x+dx] {
		res = append(res, v[p.y:p.y+dy]...)
	}
	return res
}

type Matrix [][]byte

func (m Matrix) String() string {
	res := "{\n"
	dx := len(m)
	dy := len(m[0])

	for i := 0; i < dx; i++ {
		res += "\t"
		for j := 0; j < dy; j++ {
			res += fmt.Sprintf("%2d", m[i][j])
		}
		res += "\n"
	}
	return res + "\n}"
}

func (m Matrix) Has(pat Matrix) bool {
	// Reduce our search space
	dx := len(pat)    // x-dimensions
	dy := len(pat[0]) // y-dim

	mx := len(m) - dx    // max x
	my := len(m[0]) - dy // max y

	// short paths
	if mx < 0 {
		return false
	}
	if my < 0 {
		return false
	}

	// flat pattern matrix into a vector
	pv := m2v(pat, Point{0, 0}, dx, dy)

	// For each coordinate in a search space try to fit the pattern
	// fmt.Printf("Looking for %+v in %+v...\n", pat, m)

	for i := 0; i <= mx; i++ {
		for j := 0; j <= my; j++ {
			if string(pv) == string(m2v(m, Point{i, j}, dx, dy)) {
				return true
			}
		}
	}

	return false // Unable to find a perfect fit
}

func parseDimensions(r *bufio.Reader) (dx, dy int, err error) {
	var str string
REPEAT:
	str, err = r.ReadString('\n')
	if err != nil {
		return
	}

	str = strings.Trim(str, "\n")
	if str == "" {
		goto REPEAT
	}

	// Split string on space
	// fmt.Printf("Parsing dimensions from: %q\n", str)
	t := strings.Split(str, " ")
	// fmt.Println(t)

	dx, _ = strconv.Atoi(t[1])
	dy, _ = strconv.Atoi(t[0])

	return
}

Live code - http://play.golang.org/p/Kd6tq0h4Tx