← Home
For problem statement at 1000-1999/1700-1799/1780-1789/1789/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1780-1789/1789/verifierF.go ends with wrong answer on test 7
input:
 mmhgvjuvfxbjheweo

expected:
 8

got:
 4


exit status 1 can you fix the verifier? package main

import (
	"fmt"
)

var dp2 [81][81]int
var dp3 [81][81][81]int8

type TrieNode struct {
	child   int32
	sibling int32
	char    byte
	visited bool
}

var trie []TrieNode

func getChild(u int32, ch byte) int32 {
	c := trie[u].child
	var prev int32 = -1
	for c != 0 {
		if trie[c].char == ch {
			return c
		}
		prev = c
		c = trie[c].sibling
	}
	v := int32(len(trie))
	trie = append(trie, TrieNode{char: ch})
	if prev == -1 {
		trie[u].child = v
	} else {
		trie[prev].sibling = v
	}
	return v
}

func countMatches(sub []byte, s string) int {
	count := 0
	i := 0
	n := len(s)
	m := len(sub)
	for i < n {
		j := 0
		for i < n && j < m {
			if s[i] == sub[j] {
				j++
			}
			i++
		}
		if j == m {
			count++
		}
	}
	return count
}

func main() {
	var S string
	if _, err := fmt.Scan(&S); err != nil {
		return
	}
	n := len(S)
	if n <= 1 {
		fmt.Println(0)
		return
	}

	ans := 0

	for i := 1; i < n; i++ {
		s1 := S[:i]
		s2 := S[i:]
		n1, n2 := len(s1), len(s2)
		for a := 1; a <= n1; a++ {
			for b := 1; b <= n2; b++ {
				if s1[a-1] == s2[b-1] {
					dp2[a][b] = dp2[a-1][b-1] + 1
				} else {
					mx := dp2[a-1][b]
					if dp2[a][b-1] > mx {
						mx = dp2[a][b-1]
					}
					dp2[a][b] = mx
				}
			}
		}
		l := dp2[n1][n2]
		if l*2 > ans {
			ans = l * 2
		}
	}

	for i := 1; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			s1 := S[:i]
			s2 := S[i:j]
			s3 := S[j:]
			n1, n2, n3 := len(s1), len(s2), len(s3)
			for a := 1; a <= n1; a++ {
				for b := 1; b <= n2; b++ {
					for c := 1; c <= n3; c++ {
						if s1[a-1] == s2[b-1] && s2[b-1] == s3[c-1] {
							dp3[a][b][c] = dp3[a-1][b-1][c-1] + 1
						} else {
							mx := dp3[a-1][b][c]
							if dp3[a][b-1][c] > mx {
								mx = dp3[a][b-1][c]
							}
							if dp3[a][b][c-1] > mx {
								mx = dp3[a][b][c-1]
							}
							dp3[a][b][c] = mx
						}
					}
				}
			}
			l := int(dp3[n1][n2][n3])
			if l*3 > ans {
				ans = l * 3
			}
		}
	}

	WLen := 16
	if n < 16 {
		WLen = n
	}
	trie = make([]TrieNode, 1, 100000)
	var buf [20]byte

	for start := 0; start <= n-WLen; start++ {
		w := S[start : start+WLen]
		wLen := len(w)
		var nextOcc [17][26]int
		for c := 0; c < 26; c++ {
			nextOcc[wLen][c] = -1
		}
		for i := wLen - 1; i >= 0; i-- {
			for c := 0; c < 26; c++ {
				nextOcc[i][c] = nextOcc[i+1][c]
			}
			nextOcc[i][w[i]-'a'] = i
		}

		var dfs func(wIndex int, trieIdx int32, subLen int)
		dfs = func(wIndex int, trieIdx int32, subLen int) {
			if !trie[trieIdx].visited && subLen > 0 {
				trie[trieIdx].visited = true
				c := countMatches(buf[:subLen], S)
				if c >= 2 {
					if c*subLen > ans {
						ans = c * subLen
					}
				}
			}
			for ch := byte(0); ch < 26; ch++ {
				i := nextOcc[wIndex][ch]
				if i != -1 {
					v := getChild(trieIdx, ch)
					buf[subLen] = 'a' + ch
					dfs(i+1, v, subLen+1)
				}
			}
		}
		dfs(0, 0, 0)
	}

	fmt.Println(ans)
}