ToB企服应用市场:ToB评测及商务社交产业平台

标题: LCP 与 height [打印本页]

---

作者: 梦见你的名字    时间: 2023-7-3 12:23
标题: LCP 与 height
前言

阅读此篇前，可先阅读后缀数组
LCP

LCP 就是最长公共前缀，在后缀数组中，\(LCP(i,j)\) 就代表从 \(sa_i\) 开始的后缀和从 \(sa_j\) 开始的后缀的最长公共前缀。
height 的定义

\(height=LCP(sa,sa[i-1])\)，即从 \(i\) 开始的后缀与它前一个的后缀的最长公共前缀。
一些性质

\(height[rak] \ge height[rak[i-1]]-1\)
证明：

当 \(height[rak[i-1]] \le 1\) 时，很好看出，\(height[rak] \ge 0\)，故正确。
当 \(height[rak[i-1]] > 1\) 时,因为 \(LCP(i-1,sa[rak[i-1]-1])=height[rak[i-1]] > 1\)，那么设这个最长公共为 \(aA\)（其中 \(a\) 代表一个字符 \(A\) 代表一个字符串），从 \(i-1\) 开始的后缀为 \(aAB\)，从 \(sa[rak[i-1]-1]\) 开始的后缀为 \(aAC\)，所以从 \(i\) 开始的后缀为 \(AB\)，从 \(sa[rak[i-1]-1]+1\) 开始的后缀就为 \(AC\)，所以 \(LCP(i,sa[rak[i-1]-1]+1)=|A|\)。设从 \(sa[rak-1]\) 开始的后缀就为 \(D\)。
那么因为 \(aAB > aAC\)，所以 \(AB>AC\)，因为从 \(sa[rak-1]\) 开始的后缀只比从 \(i\) 开始的后缀少一位，那么 \(AB > D \ge AC\)，所以 \(D\) 肯定有一个 \(A\) 的前缀，即 \(height[rak] \ge |A|\)，\(height[rak] \ge height[rak[i-1]]-1\)
Code

[code]void GetHeight(){        int k=0;        for(int i=1;i

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4