题解 CF1003F 【Abbreviation】

灵茶山艾府 · 2020-07-23 15:43:37 · 题解

由于操作的对象是单词，通过一个 map 把每个单词转换成数字 ID，这样题目就变成统计子区间出现次数了。由于 n 很小，可以暴力枚举子区间，查询其在序列中的出现次数，这一操作可以用 KMP 或 Rabin-Karp 来实现。

AC 代码（Golang）:

package main

import (
    "bufio"
    . "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    Fscan(in, &n)
    text := make([]int, n)  // 单词编号数组
    sum := make([]int, n+1) // 单词长度前缀和
    allSum := n - 1         // 总长度
    id := map[string]int{}
    for i := range text {
        var s string
        Fscan(in, &s)
        if _, has := id[s]; !has {
            id[s] = len(id)
        }
        text[i] = id[s]
        sum[i+1] = sum[i] + len(s)
        allSum += len(s)
    }

    // KMP: s 在 text 中的不相交出现次数
    count := func(s []int) (cnt int) {
        n := len(s)
        f := make([]int, n)
        c := 0
        for i := 1; i < n; i++ {
            b := s[i]
            for c > 0 && s[c] != b {
                c = f[c-1]
            }
            if s[c] == b {
                c++
            }
            f[i] = c
        }
        c = 0
        for _, b := range text {
            for c > 0 && s[c] != b {
                c = f[c-1]
            }
            if s[c] == b {
                c++
            }
            if c == n {
                cnt++
                c = 0
            }
        }
        return
    }

    ans := allSum
    for r := 1; r <= n; r++ {
        for l := 0; l < r; l++ {
            if c := count(text[l:r]); c > 1 {
                if v := allSum - c*(sum[r]-sum[l]-1); v < ans {
                    ans = v
                }
            }
        }
    }
    Print(ans)
}

由于 Golang 的 strings.Count 内置 Rabin-Karp，所以也可以这样写：

package main

import (
    "bufio"
    . "fmt"
    "os"
    "strings"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    Fscan(in, &n)
    a := make([]rune, n)
    sum := make([]int, n+1)
    allSum := n - 1
    id := map[string]int{}
    for i := range a {
        var s string
        Fscan(in, &s)
        if _, ok := id[s]; !ok {
            id[s] = len(id)
        }
        a[i] = rune(id[s])
        sum[i+1] = sum[i] + len(s)
        allSum += len(s)
    }

    ans := allSum
    text := string(a)
    for r := 1; r <= n; r++ {
        for l := 0; l < r; l++ {
            if c := strings.Count(text, string(a[l:r])); c > 1 {
                if v := allSum - c*(sum[r]-sum[l]-1); v < ans {
                    ans = v
                }
            }
        }
    }
    Print(ans)
}