（就是对一些严谨概念的形式化）

定义 3.1（扩展串）：将子串 \(t\) 左右扩张到最长的 \(t'\) 使得 \(t\) 与 \(t'\) 的出现次数相同，称为扩展串 \(\mathrm{ext}(t)\)。

引理 3.1：\(\mathrm{ext(t)}\) 存在且唯一。（注：这里的唯一指唯一的位置 \([l,r]\)，而非仅仅字符串唯一）

证明：设 \([l_1,r_1],[l_2,r_2]\) 是不同的最长扩展串，则 \([\min(l_1,l_2),\max(r_1,r_2)]\) 也是扩展串，矛盾。

推论 3.1：若 \(t=[l,r]\) 的扩展串为 \(t'=[l',r']\)，那么 \(t\subseteq t_0 \subseteq t'\) 的 \(t_0\) 的扩展串也是 \(t'\)。

推论 3.2：\(\mathrm{ext}(\mathrm{ext}(t))=\mathrm{ext}(t)\)。

定义 3.2（等价类）：所有 \(\mathrm{ext}(t)\) 相同的 \(t\) 形成一个等价类。

定义 3.3（代表元）：\(t=\mathrm{ext}(t)\) 的 \(t\) 称为该等价类的代表元，记做 \(\mathrm{rep}(a)\)。

引理 3.2：每个等价类的代表元唯一。（显然）

引理 3.3：若 \(t_1\subseteq t_2\) 且 \(\mathrm{occ}(t_1)=\mathrm{occ}(t_2)\)，则 \(\mathrm{ext}(t_1)=\mathrm{ext}(t_2)\)。

证明：\(t_1\subseteq t_2\subseteq \mathrm{ext}(t_2)\)，\(\mathrm{occ}(t_1)=\mathrm{occ}(t_2)=\mathrm{occ}(\mathrm{ext}(t_2))\)，\(\nexists t'\supsetneq \mathrm{ext}(t_2),\mathrm{occ}(t')=\mathrm{occ}(\mathrm{ext}(t_2))\)，故 \(\mathrm{ext}(t_1)=\mathrm{ext}(t_2)\)。

定义 3.4：定义 \(t\) 在 \(s\) 中第一次出现位置为 \(s[\mathrm{posl}(t),\mathrm{posr}(t)]\)。

定理 3.1：以 \(l,r\) 为轴建立平面直角坐标系，则对于等价类 \(a\)，其元素的 \((\mathrm{posl},\mathrm{posr})\) 构成的点集在平面上形成一个上端与左端对齐的阶梯。

证明：\(t\) 的首次出现的位置与 \(\mathrm{ext}(t)\) 首次出现的位置对应，且由推论 3.1 可知一个点 \(t\) 为右下角，\(\mathrm{rep}(a)\) 为的矩形内的点都属于等价类 \(a\)，证毕。

推论 3.3：平面上 \(1\le l\le r\le n\) 的点被划分为若干个互不相交的阶梯，每个等价类 \(a\) 对应于其中 \(\mathrm{occ}(\mathrm{rep}(a))\) 个形状相同的阶梯。（注：由引理 3.1 可得同一 \(a\) 之间的阶梯也不相交）

定义 3.5（周长）：定义一个等价类 \(a\) 的周长 \(\mathrm{per}(a)\) 为其所对应的阶梯行数与列数之和。

Note：以下也将一个等价类称为一块。

定理 3.2：对于每一个等价类 \(a\)，在其对应的阶梯中，每一行（\(r\) 相同）对应正 \(\mathrm{SAM}\) 上一个节点，每一列（\(l\) 相同）对应于反 \(\mathrm{SAM}\) 上一个节点，且所有等价类的所有行与正 \(\mathrm{SAM}\) 的所有节点一一对应，所有列与反 \(\mathrm{SAM}\) 的所有节点一一对应。“对应”指字符串集合相同。

证明：以下只证明行的部分，列的部分同理。对于一块中的一行，\(r\) 不变，\(\mathrm{occ}\) 不变，因此都在同一个正 \(\mathrm{SAM}\) 节点上；对于正 \(\mathrm{SAM}\) 的一个节点，其所有字符串 \(\mathrm{occ}\) 相同，因此在同一块内，\(r\) 相同，因此在同一行中。证毕。

定理 3.3：所有块的周长之和为 \(O(n)\)。（即正反串 \(\mathrm{SAM}\) 的节点数之和）

Note：最后将正反串 \(parent\) 树的树边补上去，只用将每列的