Submission #59181534

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main
import (
  "bufio"
  "fmt"
  stdio "io"
  "os"
  "strconv"
)
var io *Iost
type Iost struct {
  Scanner *bufio.Scanner
  Writer  *bufio.Writer
}
func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
  const BufSize = 2000005
  scanner := bufio.NewScanner(fp)
  scanner.Split(bufio.ScanWords)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

package main

import (
	"bufio"
	"fmt"
	stdio "io"
	"os"
	"strconv"
)

var io *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (io *Iost) Text() string {
	if !io.Scanner.Scan() {
		panic("scan failed")
	}
	return io.Scanner.Text()
}
func (io *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (io *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (io *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (io *Iost) NextInt() int                      { return io.Atoi(io.Text()) }
func (io *Iost) NextInt64() int64                  { return io.Atoi64(io.Text()) }
func (io *Iost) NextFloat64() float64              { return io.Atof64(io.Text()) }
func (io *Iost) Print(x ...interface{})            { fmt.Fprint(io.Writer, x...) }
func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) }
func (io *Iost) Println(x ...interface{})          { fmt.Fprintln(io.Writer, x...) }

const INF int = 1e18

type TrieNode struct {
	PreCount  int
	WordCount int
	MinLen    int
	Parent    *TrieNode
	Children  map[byte]*TrieNode
}

func NewTrieNode(parent *TrieNode) *TrieNode {
	return &TrieNode{
		MinLen:   INF,
		Parent:   parent,
		Children: make(map[byte]*TrieNode),
	}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: NewTrieNode(nil),
	}
}

func (t *Trie) Insert(s []byte) {
	if len(s) == 0 {
		return
	}
	root := t.root
	for i := 0; i < len(s); i++ {
		char := s[i]
		if _, ok := root.Children[char]; !ok {
			root.Children[char] = NewTrieNode(root)
		}
		root.Children[char].PreCount++
		root = root.Children[char]
		root.MinLen = min(root.MinLen, len(s))
	}
	root.WordCount++
}

func main() {
	in := os.Stdin
	out := os.Stdout
	io = NewIost(in, out)
	defer func() {
		io.Writer.Flush()
	}()

	N := io.NextInt()
	words := make([]string, N)
	for i := 0; i < N; i++ {
		words[i] = io.Text()
	}

	trie := NewTrie()

	query := func(s []byte) int {
		res := len(s)

		root := trie.root
		for i := 0; i < len(s); i++ {
			char := s[i]
			if _, ok := root.Children[char]; !ok {
				return res
			}
			root = root.Children[char]
			if root.PreCount > 0 {
				lcp := i + 1
				res = min(res, root.MinLen+len(s)-2*lcp)
			}
		}
		return res
	}

	for i := 0; i < N; i++ {
		io.Println(query([]byte(words[i])))
		trie.Insert([]byte(words[i]))
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func mins(nums ...int) int {
	res := nums[0]
	for _, num := range nums {
		if num < res {
			res = num
		}
	}
	return res
}

func maxs(nums ...int) int {
	res := nums[0]
	for _, num := range nums {
		if num > res {
			res = num
		}
	}
	return res
}

Submission Info

Judge Result