OSDN Git Service

在manacher.md中,增加 d1[i], d2[i] 也表示最长回文串半径的描述
author徐伟 <readOnlyFile@hotmail.com>
Sat, 5 Dec 2020 13:27:48 +0000 (21:27 +0800)
committerGitHub <noreply@github.com>
Sat, 5 Dec 2020 13:27:48 +0000 (21:27 +0800)
commitfc62de868762bc029820c032f0fbb46c84e6f45f
treeedc937413f604bbccd0bb422d07a7b9b329b3d21
parent8d08d6d22d96b989971edb2727212f6558687950
在manacher.md中,增加 d1[i], d2[i] 也表示最长回文串半径的描述

关键改动: 增加 d1[i], d2[i] 也表示最长回文串半径的描述
改动原因:原文仅说明 d1[i], d2[i]为 以i为中心,包含的回文串个数。这个定义与 开篇的描述 `请找到所有对 $(i, j)$ 使得子串 $s[i \dots j]$ 为一个回文串` 是相符的,但是对 manacher 算法也无关。因为 manacher 算法中,该值是取 「半径」的含义,进而可以做 位置的加减。之前没有明确点出该含义,对理解算法会有一点影响。
——————
其他改动: 对 `r = -1` 的初值做了额外说明。因为 Python 等语言中,`-1` 会表示反向索引,这与 r 的初值本意不符,又会引来一定歧义。尽管在 C 系世界/OI 语境 中,这理论上不会 有 问题,但是考虑到受众,或许加上一点说明也无妨。
docs/string/manacher.md