AtCoder ABC054 B - Template Matching

AtCoderに取り組んだ記録です。
AtCoder ProblemsのRecommendationsからピックアップして解いています。

問題ページはこちらです。
Point: 200
Difficulty: 828

考えたこと

左上から始点の画素を固定して、画像Bと全画素が一致するかをチェックすれば行けそうな気がします。制約もN, Mともに50以下なので間に合いそうです。

・画像Aの全画素について、左上から始点となる画素を決める
・決めた画素から、画像Bと同じ画像の面積（？）分の全画素が画像Bのものと一致するかをチェックする
・全画素が一致するものがみつかれば "Yes"、みつからなければ"No"

提出したコード

提出ページ

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(r, &n)
	fmt.Fscan(r, &m)

	a := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a[i])
	}
	b := make([]string, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(r, &b[i])
	}

	ans := false
	for i := 0; i < n-m+1; i++ {
		for j := 0; j < n-m+1; j++ {
			if check(i, j, a, b) {
				ans = true
				break
			}
		}
	}

	if ans {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func check(startI, startJ int, a, b []string) bool {
	result := true
	for i := 0; i < len(b); i++ {
		for j := 0; j < len(b); j++ {
			if a[i+startI][j+startJ] != b[i][j] {
				result = false
				break
			}
		}
	}
	return result
}

感想など

・Difficultyに比べて少し易しい問題な印象

・解説に以下の計算量が記載されていた

全探索を行ったときの時間計算量は O(N2M2) となり、これは間に合います。

始点を決定するために、Nの2乗（縦*横）、画素のチェック処理にMの2乗（縦*横）が必要ということなのか。どうしてもふんわりとした理解で提出しがちです。が、このくらいわかりやすいものは、しっかりと計算量を把握した上で提出したいところ。。

・数式ってどうやってnoteにどうやって書くんだろうか。。調べないと