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$ 若按零起算的出现编号记为 $k=Occ(c,i)$，first–last property 说明它对应 $F$ 中同样编号为 $k$ 的 $c$，位置正是 $C[c]+k$。反向区间公式只是把区间内所有 $c$ 出现的编号范围映到这段 $F$ 区间。

定位时取整数 $1\le s\le n$，保存所有满足 $SA[i]\equiv 0(\mathrm{mod}s)$ 的行。每次 LF 令 $SA$ 值减一模 $n$，所以至多 $s-1$ 步就遇到样本；把步数加回样本值并模 $n$，即恢复原位置。一次 LF 还要读取 $L[i]$ 和 $C[L[i]]$，这些访问与样本判定都须纳入单步成本。

按“每第 $s$ 行”取样则没有这个保证。例如 bacedf$ 的 $SA=(6,1,0,2,4,3,5)$，取偶数行样本，值为 $3$ 的行要连续走过 $2,1$ 才到样本值 $0$，共三步。更一般地，可让 $k$ 个连续 SA 值都位于奇数行，采样行距固定为二，LF 仍需 $k$ 步。保证来自文本位置的间隔，而非排序后行号的间隔。

区间收缩的数值核对 ​

假设当前区间 $[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$ 条定位路径，在 rank、LF 与样本查询均为常数成本时，时间可写成 $O(|P|+1+occ\cdot s)$，而非把 count 的 $O(|P|)$ 误报为完整检索成本。