← Home
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)
}
```