← Home
For problem statement at 0-999/200-299/260-269/264/problemD.txt this is a correct solution, but verifier at 0-999/200-299/260-269/264/verifierD.go ends with case 1 failed
expected:
7

got:
14

exit status 1 can you fix the verifier? ```go
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

// fast IO
var reader *bufio.Reader
var writer *bufio.Writer

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var s, t string
	fmt.Fscan(reader, &s)
	fmt.Fscan(reader, &t)

	n := len(s)
	m := len(t)

	// Forward BFS
	L := bfs(s, t)

	// Reverse strings
	sr := reverse(s)
	tr := reverse(t)

	// Backward BFS
	Lr := bfs(sr, tr)

	ans := int64(0)
	K := n - m
	offset := m + 5
	sz := n + m + 10

	for k := -m; k <= n; k++ {
		idx := k + offset
		if idx < 0 || idx >= sz {
			continue
		}
		l_val := L[idx]
		if l_val > n+1 { // Infinity check
			continue
		}

		k_rev := K - k
		idx_rev := k_rev + offset
		if idx_rev < 0 || idx_rev >= len(Lr) {
			continue
		}
		lr_val := Lr[idx_rev]
		if lr_val > n+1 {
			continue
		}

		// Calculate max reachable i (u_val)
		// i <= N + 2 - x
		u_val := n + 2 - lr_val

		if u_val >= l_val {
			ans += int64(u_val - l_val + 1)
		}
	}

	fmt.Fprintln(writer, ans)
}

func reverse(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

const INF = 1e9

// Hashing
const P1 = 131
const M1 = 1000000007
const P2 = 13331
const M2 = 1000000009

type Hash struct {
	h1, h2 []int64
	p1, p2 []int64
}

func buildHash(s string) *Hash {
	n := len(s)
	h1 := make([]int64, n+1)
	h2 := make([]int64, n+1)
	p1 := make([]int64, n+1)
	p2 := make([]int64, n+1)
	p1[0] = 1
	p2[0] = 1
	for i := 0; i < n; i++ {
		p1[i+1] = (p1[i] * P1) % M1
		p2[i+1] = (p2[i] * P2) % M2
		c := int64(s[i])
		h1[i+1] = (h1[i]*P1 + c) % M1
		h2[i+1] = (h2[i]*P2 + c) % M2
	}
	return &Hash{h1, h2, p1, p2}
}

func (h *Hash) get(l, r int) (int64, int64) {
	len := r - l + 1
	v1 := (h.h1[r] - h.h1[l-1]*h.p1[len]) % M1
	if v1 < 0 {
		v1 += M1
	}
	v2 := (h.h2[r] - h.h2[l-1]*h.p2[len]) % M2
	if v2 < 0 {
		v2 += M2
	}
	return v1, v2
}

// Priority Queue implementation
type Item struct {
	u        int
	priority int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int            { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool  { return pq[i].priority < pq[j].priority }
func (pq PriorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func bfs(s, t string) []int {
	n := len(s)
	m := len(t)
	offset := m + 5
	sz := n + m + 10
	dist := make([]int, sz)
	for i := range dist {
		dist[i] = INF
	}

	pq := &PriorityQueue{}
	heap.Init(pq)

	dist[offset] = 1
	heap.Push(pq, Item{u: 0, priority: 1})

	hs := buildHash(s)
	ht := buildHash(t)

	getLCP := func(i, j int) int {
		r := n
		if n-i+1 < r {
			r = n - i + 1
		}
		if m-j+1 < r {
			r = m - j + 1
		}
		ans := 0
		lo, hi := 1, r
		for lo <= hi {
			mid := (lo + hi) / 2
			s1, s2 := hs.get(i, i+mid-1)
			t1, t2 := ht.get(j, j+mid-1)
			if s1 == t1 && s2 == t2 {
				ans = mid
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
		return ans
	}

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		u := item.u
		d := item.priority

		if d > dist[u+offset] {
			continue
		}

		i := d
		j := i - u

		if i > n || j > m {
			continue
		}

		lcp := getLCP(i, j)
		ni := i + lcp
		nj := j + lcp

		if ni > n || nj > m {
			continue
		}

		// Try moving t (u-1)
		v1 := u - 1
		if v1+offset >= 0 && v1+offset < sz {
			if dist[v1+offset] > ni {
				dist[v1+offset] = ni
				heap.Push(pq, Item{u: v1, priority: ni})
			}
		}

		// Try moving s (u+1)
		v2 := u + 1
		if v2+offset >= 0 && v2+offset < sz {
			if dist[v2+offset] > ni+1 {
				dist[v2+offset] = ni + 1
				heap.Push(pq, Item{u: v2, priority: ni + 1})
			}
		}
	}
	return dist
}
```