For problem statement at 0-999/100-199/110-119/119/problemD.txt this is a correct solution, but verifier at 0-999/100-199/110-119/119/verifierD.go ends with All tests passed can you fix the verifier? ```go
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
// Read string a
line1, err := reader.ReadBytes('\n')
if err != nil && len(line1) == 0 {
return
}
a := strip(line1)
// Read string b
line2, err := reader.ReadBytes('\n')
if err != nil && len(line2) == 0 {
// Proceed if data exists
}
b := strip(line2)
n := len(a)
// If lengths differ or n < 2, impossible (since i < j < n implies n >= 2)
if len(b) != n || n < 2 {
fmt.Fprintln(writer, "-1 -1")
return
}
// rb is reverse of b
rb := reverse(b)
// Special case: if a equals reverse(b), then s=0 is valid for any k.
// This corresponds to an empty middle part.
// We want max i. The condition a == rb allows picking max possible i = n-2, j = n-1.
if bytes.Equal(a, rb) {
fmt.Fprintf(writer, "%d %d\n", n-2, n-1)
return
}
// Standard case: s >= 1.
ra := reverse(a)
// Calculate Z-array for b + # + a to get LCP(a[k...], b)
// Concatenation: b (len n) + 0 + a (len n)
s1 := make([]byte, 0, 2*n+1)
s1 = append(s1, b...)
s1 = append(s1, 0)
s1 = append(s1, a...)
z1 := zFunction(s1)
// lcpAB[k] = LCP(a[k...], b)
lcpAB := make([]int, n)
for i := 0; i < n; i++ {
lcpAB[i] = z1[n+1+i]
}
// Calculate Z-array for ra + # + b to get LCP(ra, b[s...])
// Concatenation: ra (len n) + 0 + b (len n)
s2 := make([]byte, 0, 2*n+1)
s2 = append(s2, ra...)
s2 = append(s2, 0)
s2 = append(s2, b...)
z2 := zFunction(s2)
// lcpRAB[s] = LCP(ra, b[s...])
lcpRAB := make([]int, n)
for i := 0; i < n; i++ {
lcpRAB[i] = z2[n+1+i]
}
// Calculate max prefix match between a and rb
// We need a[0...k-1] == rb[0...k-1]
kLimit := 0
for kLimit < n && a[kLimit] == rb[kLimit] {
kLimit++
}
// Build Segment Tree for range maximum query on vals[s] = s + lcpRAB[s]
// vals index s from 1 to n-1
vals := make([]int, n)
for s := 1; s < n; s++ {
vals[s] = s + lcpRAB[s]
}
st := newSegmentTree(vals)
// Iterate k from max possible down to 1
// Max i is determined by i < j < n => i <= n-2. So k = i+1 <= n-1.
// Start k limited by prefix match length kLimit
startK := n - 1
if kLimit < startK {
startK = kLimit
}
for k := startK; k >= 1; k-- {
// Valid s range:
// 1. s >= 1
// 2. s <= lcpAB[k] (middle part matches)
// 3. k + s < n => s <= n - k - 1
limitS := lcpAB[k]
if n-k-1 < limitS {
limitS = n - k - 1
}
if limitS < 1 {
continue
}
// Query for smallest s in [1, limitS] such that s + lcpRAB[s] >= n - k
target := n - k
s := st.queryFirst(1, 0, n-1, 1, limitS, target)
if s != -1 {
// Found valid s, which minimizes j for this k (since s is minimal)
// k is maximal because we iterate downwards
fmt.Fprintf(writer, "%d %d\n", k-1, k+s)
return
}
}
fmt.Fprintln(writer, "-1 -1")
}
func strip(b []byte) []byte {
for len(b) > 0 && (b[len(b)-1] == '\n' || b[len(b)-1] == '\r') {
b = b[:len(b)-1]
}
return b
}
func reverse(s []byte) []byte {
r := make([]byte, len(s))
for i := 0; i < len(s); i++ {
r[i] = s[len(s)-1-i]
}
return r
}
func zFunction(s []byte) []int {
n := len(s)
z := make([]int, n)
l, r := 0, 0
for i := 1; i < n; i++ {
if i <= r {
min := r - i + 1
if z[i-l] < min {
min = z[i-l]
}
z[i] = min
}
for i+z[i] < n && s[z[i]] == s[i+z[i]] {
z[i]++
}
if i+z[i]-1 > r {
l = i
r = i + z[i] - 1
}
}
return z
}
type SegmentTree struct {
n int
tree []int
}
func newSegmentTree(data []int) *SegmentTree {
n := len(data)
tree := make([]int, 4*n)
st := &SegmentTree{n, tree}
st.build(data, 1, 0, n-1)
return st
}
func (st *SegmentTree) build(data []int, node, start, end int) {
if start == end {
st.tree[node] = data[start]
} else {
mid := (start + end) / 2
st.build(data, 2*node, start, mid)
st.build(data, 2*node+1, mid+1, end)
if st.tree[2*node] > st.tree[2*node+1] {
st.tree[node] = st.tree[2*node]
} else {
st.tree[node] = st.tree[2*node+1]
}
}
}
// queryFirst finds the smallest index in [l, r] such that vals[index] >= val
func (st *SegmentTree) queryFirst(node, start, end, l, r, val int) int {
if start > end || start > r || end < l {
return -1
}
// Optimization: if max value in this range is less than val, no solution here
if st.tree[node] < val {
return -1
}
if start == end {
return start
}
mid := (start + end) / 2
// Try left child first to find smallest index
res := st.queryFirst(2*node, start, mid, l, r, val)
if res != -1 {
return res
}
return st.queryFirst(2*node+1, mid+1, end, l, r, val)
}
```