AtCoder ABC 141 E - Who Says a Pun? (Go) ※嘘解法 - あるエンジニアのAtCoder奮闘記

irisruneです。実行時間1945msはかなり攻めた嘘解法だと思いました。

問題

一見愚直に解けそうに見えますが工夫が必要な問題です。

package main

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

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type node struct {
    len      int
    idxs     []int
    children map[rune](*node)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, s := nextInt(), nextStr()
    rs := []rune(s)

    root := node{0, make([]int, n), make(map[rune](*node), 0)}
    for i := 0; i < n; i++ {
        root.idxs[i] = i
    }
    queue := []*node{&root}
    ans := 0
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        if cur.idxs[len(cur.idxs)-1]-cur.idxs[0] < cur.len {
            continue
        }
        ans = cur.len
        for _, idx := range cur.idxs {
            if idx+cur.len >= n {
                continue
            }
            r := rs[idx+cur.len]
            child, ok := cur.children[r]
            switch {
            case ok:
                child.idxs = append(child.idxs, idx)
            default:
                child = &(node{cur.len + 1, []int{idx}, make(map[rune](*node), 0)})
            }
            cur.children[r] = child
        }
        for _, child := range cur.children {
            queue = append(queue, child)
        }
    }

    fmt.Println(ans)
}

制約上、計算量が $O(N^2)$ であれば十分間に合います。そして $S$ の連続する部分文字列の数は $O(N^2)$ であるため、各部分文字列の位置と合わせて記憶しつつ文字列比較を行うことで愚直に解くことができそうです。

しかし単純な文字列比較を行うための計算量は $O(N)$ であるため、全体の計算量は $O(N^3)$ となってしまい到底間に合いません。文字列比較にローリングハッシュを用いるという解法が公式解説にて別解として示されていますが、今回は別の手法で解きました。

今回の手法は枝刈りBFSに近いものです。探索木の構造としては、右端を $S$ の右端に固定した $N$ 個の部分文字列について、1文字目の文字種毎に開始位置の集合を節点として持ち、その子として2文字目の文字種毎に開始位置の集合を節点として持ち…という構造になっています。ちなみに探索木の根は0文字目の文字種（当然そのようなものはないため空あるいは任意文字とでも定義します）に対する開始位置の集合 $(1,2,\ldots,N)$ です。

探索にかかる計算量は節点ごとの集合の要素数の和の定数倍となります。枝刈りを無視すると各階層毎に合計 $N$ 個の要素（部分文字列）があるので、計算量は $O(N^2)$ と推測されます。しかし実行時間が2秒近いことを考えるとどこかに見落としがあるか、あるいは定数倍の部分で計算量が増大しているかもしれません。

枝刈りによって階層毎の要素数が $N/1,N/2,\ldots,N/N$ と減少していくので（実際は要素数が2を下回る節点そのものが枝刈りされるためもっと減ります）、計算量は $O(N\log N)$ と推測することもできますが、明らかに実行時間やループ回数に見合っていないのでおそらく正しい推察ではありません。

雑記

上記コードで各節点に子の集合を持たせようとはしていますが、特に意味はなかったことに気付きました。
初めてZ-Algorithmというものの存在を知りました、内容はまだ殆ど理解していないです。
- セグメント木を理解していなかったりなど知識面で躓くことは多いので、難しめの問題に必要なアルゴリズムやデータ構造も身に付けたいです。