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