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
}
```