Golang Aho Corasick DP
Aho Corasick\n\npackage main\n\nvar dp [5e4 + 1]int\n\nfunc minValidStrings(words []string, target string) int {\n\tn := len(target)\n\troot := buildTrie(words)
# Aho Corasick\n```\npackage main\n\nvar dp [5e4 + 1]int\n\nfunc minValidStrings(words []string, target string) int {\n\tn := len(target)\n\troot := buildTrie(words)\n\tcomputeSuffix(root)\n\n\tcurrent := root\n\tfor i := 1; i <= len(target); i++ {\n\t\tch := target[i-1] - \'a\'\n\n\t\tfor current.child[ch] == nil && root != current {\n\t\t\tcurrent = current.suffix\n\t\t}\n\n\t\tcurrent = current.child[ch]\n\t\tif current == nil {\n\t\t\treturn -1\n\t\t}\n\n\t\t// Longest suffix in target[:i] that is prefix in Trie\n\t\tsuffixLength := current.length\n\n\t\tdp[i] = 1 + dp[i-suffixLength]\n\t}\n\n\treturn dp[n]\n}\n\ntype Trie struct {\n\tchild  []*Trie\n\tsuffix *Trie\n\tlength int\n}\n\nfunc NewTrie() *Trie {\n\treturn &Trie{child: make([]*Trie, 26)}\n}\n\nfunc buildTrie(words []string) *Trie {\n\troot := NewTrie()\n\tfor _, word := range words {\n\t\tcurrent := root\n\t\tl := 0\n\t\tfor _, ch := range word {\n\t\t\tch = ch - \'a\'\n\t\t\tif current.child[ch] == nil {\n\t\t\t\tcurrent.child[ch] = NewTrie()\n\t\t\t}\n\t\t\tl++\n\t\t\tcurrent = current.child[ch]\n\t\t\tcurrent.length = l\n\t\t}\n\t}\n\treturn root\n}\n\nfunc computeSuffix(root *Trie) {\n\troot.suffix = root\n\tqueue := []*Trie{root}\n\n\tfor len(queue) > 0 {\n\t\tparent := queue[0]\n\t\tqueue = queue[1:]\n\n\t\tfor i := 0; i < 26; i++ {\n\t\t\tchild := parent.child[i]\n\t\t\tif child == nil {\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\ts := parent.suffix\n\t\t\tfor s != root && s.child[i] == nil {\n\t\t\t\ts = s.suffix\n\t\t\t}\n\t\t\tif s.child[i] != nil && parent != root {\n\t\t\t\tchild.suffix = s.child[i]\n\t\t\t} else {\n\t\t\t\tchild.suffix = root\n\t\t\t}\n\t\t\tqueue = append(queue, child)\n\t\t}\n\t}\n}\n\n```\n\n\n---\n\n# Max LPS\n\n```\npackage main\n\nvar dp [5e4 + 1]int\nvar lps [1e5 + 2]int\n\nfunc minValidStrings(words []string, target string) int {\n\tn := len(target)\n\tmaxPrefix := make([]int, n)\n\n\tfor _, word := range words {\n\t\tmaxLps(maxPrefix, word, target)\n\t}\n\n\tfor i := 1; i <= n; i++ {\n\t\tprev := i - maxPrefix[i-1]\n\t\tif prev == i {\n\t\t\treturn -1\n\t\t}\n\t\tdp[i] = 1 + dp[prev]\n\t}\n\n\treturn dp[n]\n}\n\nfunc maxLps(maxPrefix []int, word string, target string) {\n\tl1 := len(word)\n\tstr := word + "$" + target\n\n\tfor i := 1; i < len(str); i++ {\n\t\tlps[i] = lps[i-1]\n\t\tfor lps[i] != 0 && str[i] != str[lps[i]] {\n\t\t\tlps[i] = lps[lps[i]-1]\n\t\t}\n\t\tif str[i] == str[lps[i]] {\n\t\t\tlps[i]++\n\t\t}\n\t}\n\n\tfor i := 0; i < len(target); i++ {\n\t\tmaxPrefix[i] = max(maxPrefix[i], lps[i+l1+1])\n\t}\n}\n\n\n\n\n```
['Go']