LF 映射与反向搜索

排序后的后缀把同一前缀聚成连续区间。BWT 末列记录每个后缀左边的字符，first–last 对应又保持相同字符的出现次序；因此统计当前区间内字符 $c$ 的 occurrence rank，就能一次把整段后缀统一向左扩展。

banana$ 例子 ​

在文本 banana$ 的 BWT 上搜索 ana：先由字符 a 得到所有 a 开头后缀的区间，再用 n 收缩为 na，最后用 a 收缩为 ana。某一步左右端相等即为空区间，之后模式不存在；不能继续把负长度或闭区间端点代入。

边界与逆映射 ​

字符表次序决定 $C$，终止符必须唯一且最小。同一字符的第 $k$ 次出现必须稳定对应，否则 LF 不再沿文本向前一位。LF 与 $\mathrm{\Psi }$ 是方向相反的相关映射，不应混写公式。正文只给 count 区间；定位原文位置还需后缀数组采样及 LF 步进成本。

C 数组是字符总频率的前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。：C[c] 给出首列中严格小于 c 的字符数，再与 rankc(L,i) 相加定位同一字符的稳定次序。

公式证明与定位 ​

$F$ 中字符 $c$ 占据从 $C[c]$ 开始的连续区间。$L[i]=c$ 若是 $L$ 中第 $k$ 次出现（按半开 rank，$k=Occ(c,i)$），first–last property 说明它对应 $F$ 中第 $k$ 个 $c$，位置正是 $C[c]+k$。反向区间公式只是把区间内所有 $c$ 出现的编号范围映到这段 $F$ 区间。

FM-index 每隔 $s$ 行存一次 suffix-array 值。定位某匹配行时反复 LF，直到命中样本，并按步数修正文本位置，最坏需 $O(s)$ 次 rank；采样越密，定位快但空间更大。Count、locate 与 extract 因而有不同成本。

区间收缩的数值核对 ​

假设当前区间 $[l,r)=[2,6)$，要向左扩展字符 a，且 $C[a]=1$、$Occ(a,2)=1$、$Occ(a,6)=3$。新区间是 $[2,4)$，长度 2 正好等于原区间对应 BWT 片段中 a 的出现数 $3-1$。这个长度守恒是排查端点错误最直接的断言。

逐字符搜索只得到 suffix-array 行区间；若要输出文本位置，需对每一行沿 LF 走到最近采样行。一个匹配很多的模式会产生 $occ$ 条定位路径，所以成本应写成 $O(|P|+occ\cdot s)$ 的朴素上界，而非把 count 的 $O(|P|)$ 误报为完整检索成本。