← Home
For problem statement at 0-999/900-999/950-959/958/problemA2.txt this is a correct solution, but verifier at 0-999/900-999/950-959/958/verifierA2.go ends with All 158 tests passed can you fix the verifier? ```go
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	var N, M int
	fmt.Sscanf(scanner.Text(), "%d %d", &N, &M)
	A := make([]string, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		A[i] = scanner.Text()
	}
	B := make([]string, M)
	for i := 0; i < M; i++ {
		scanner.Scan()
		B[i] = scanner.Text()
	}
	const base uint64 = 131
	const mod1 uint64 = 1000000007
	const mod2 uint64 = 1000000009
	pow1 := make([]uint64, M+1)
	pow1[0] = 1
	for i := 1; i <= M; i++ {
		pow1[i] = pow1[i-1] * base % mod1
	}
	pow2 := make([]uint64, M+1)
	pow2[0] = 1
	for i := 1; i <= M; i++ {
		pow2[i] = pow2[i-1] * base % mod2
	}
	hA1 := make([]uint64, N)
	for p := 0; p < N; p++ {
		var h uint64 = 0
		for c := 0; c < M; c++ {
			val := uint64(A[p][c] - 'a' + 1)
			h = (h * base + val) % mod1
		}
		hA1[p] = h
	}
	hA2 := make([]uint64, N)
	for p := 0; p < N; p++ {
		var h uint64 = 0
		for c := 0; c < M; c++ {
			val := uint64(A[p][c] - 'a' + 1)
			h = (h * base + val) % mod2
		}
		hA2[p] = h
	}
	pre1 := make([][]uint64, M)
	pre2 := make([][]uint64, M)
	for q := 0; q < M; q++ {
		pre1[q] = make([]uint64, N+1)
		pre1[q][0] = 0
		for c := 1; c <= N; c++ {
			val := uint64(B[q][c-1] - 'a' + 1)
			pre1[q][c] = (pre1[q][c-1] * base + val) % mod1
		}
		pre2[q] = make([]uint64, N+1)
		pre2[q][0] = 0
		for c := 1; c <= N; c++ {
			val := uint64(B[q][c-1] - 'a' + 1)
			pre2[q][c] = (pre2[q][c-1] * base + val) % mod2
		}
	}
	m := make(map[[2]uint64][]int)
	for jj := 0; jj <= N-M; jj++ {
		var win_h1 uint64 = 0
		var win_h2 uint64 = 0
		for q := 0; q < M; q++ {
			L := jj
			R := jj + M - 1
			row_h1 := (pre1[q][R+1] + mod1 - pre1[q][L]*pow1[M]%mod1) % mod1
			row_h2 := (pre2[q][R+1] + mod2 - pre2[q][L]*pow2[M]%mod2) % mod2
			win_h1 = (win_h1 * base + row_h1) % mod1
			win_h2 = (win_h2 * base + row_h2) % mod2
		}
		key := [2]uint64{win_h1, win_h2}
		m[key] = append(m[key], jj+1)
	}
	for ii := 0; ii <= N-M; ii++ {
		var win_h1 uint64 = 0
		var win_h2 uint64 = 0
		for k := 0; k < M; k++ {
			rh1 := hA1[ii+k]
			rh2 := hA2[ii+k]
			win_h1 = (win_h1 * base + rh1) % mod1
			win_h2 = (win_h2 * base + rh2) % mod2
		}
		key := [2]uint64{win_h1, win_h2}
		if js, ok := m[key]; ok {
			for _, j := range js {
				match := true
				for row := 0; row < M && match; row++ {
					arow := A[ii+row]
					bsub := B[row][j-1 : j-1+M]
					if arow != bsub {
						match = false
					}
				}
				if match {
					fmt.Println(ii+1, j)
					return
				}
			}
		}
	}
}
```