Ukkonen算法中Gusfield的β与jogojapan的活跃点是否对应？

Yes, Gusfield's β (B) directly maps to the "active point" concept in Ukkonen's optimized implementation—but the gap between the formal, unoptimized algorithm (Gusfield) and the practical, optimized code (jogojapan's demo) is what's throwing you off. Let's unpack this step by step, because this is a super common hurdle when moving from theory to code.

困惑1：j=i+1时，β=S[j..i]是无效区间 #

This is a deliberate abstraction in Gusfield's writing to keep the algorithm's structure consistent! When j=i+1, β is indeed the empty string, which corresponds directly to the root node. But here's the key: Gusfield's "extension j" for j=i+1 doesn't require an actual traversal—it's the logical starting point for the next batch of suffix expansions. The active point optimization captures this by carrying over state from the previous stage, so we don't have to explicitly start at the root for every new stage.

Gusfield's algorithm is a naive, step-by-step expansion of every suffix up to the current character. Ukkonen's active point skips all the redundant work of processing suffixes that only need rule 1 (extending existing leaves). So when j=i+1, β being empty is exactly the root (the initial active point for the stage)—but in practice, we don't need to process this "extension" because the active point logic already accounts for it.

困惑2：假设β为空串对应根节点，插入点与活跃点冲突 #

The "conflict" you're seeing comes from the difference between the unoptimized and optimized approaches:

• In Gusfield's algorithm, every suffix extension (j from 1 to i+1) is processed in order. For j=i+1, β is empty, so we start at the root and look for an edge starting with S[i+1].
• In jogojapan's implementation, the active point is already positioned to handle the first suffix that actually needs rule 2 or 3 (not the dozens that just need rule 1). The active point doesn't match every j in Gusfield's loop—it's a shortcut that skips all the rule 1 steps entirely.

Your assumption that β=empty maps to the root is correct—but the active point isn't meant to align with every j in Gusfield's formal loop. It's optimized to only track the suffixes that require non-trivial processing.

困惑3：推理每个阶段仅一次后缀插入（规则2/3），其余规则1，导致插入只能从根开始，与规则2矛盾 #

Your reasoning is almost right—you just missed how the active point maintains state between non-rule-1 steps! Here's the correction:

1. Most suffixes in a stage trigger rule 1 (extending leaves). Ukkonen's algorithm handles this with the global end index trick, so we don't have to touch each leaf individually. The active point stays put during these steps.
2. When we hit a suffix that needs rule 2 (inserting a new leaf edge) or rule 3 (splitting an edge to insert a new node), the active point is already at the exact position (active node + active edge + active length) to perform that insertion—no need to traverse from the root.
3. Gusfield's algorithm describes this as looping j until we hit a suffix that needs rule 2/3—but the active point optimization lets us jump directly to that j, skipping all the redundant rule 1 processing.

Rule 2's edge insertion doesn't have to start from the root every time. Gusfield's formal description includes the root traversal for every j, but the active point keeps us anchored at the right spot from the last non-rule-1 operation.

To bridge Gusfield's theory and jogojapan's code, think of it this way:

• Gusfield's β for each j is the suffix we're trying to extend. The active point is the condensed state (active node, edge, length) that represents the longest suffix we haven't yet processed with rule 1.
• Every time we apply rule 2 or 3, we update the active point (using suffix links) to reflect the next suffix that needs processing—this corresponds to moving to the β for the next j in Gusfield's loop.
• The global end index in Ukkonen's code replaces Gusfield's explicit update of all leaves for rule 1.

Your initial reasoning wasn't wrong—it just didn't account for how the active point optimization collapses the repetitive parts of Gusfield's loop into a single, dynamically updated state.

内容的提问来源于stack exchange，提问作者Jon Badiali