Properties and Observations
Keep the notation from the first lesson: is the suffix link of state , and consumes character . Patterns are nonempty. Let be their total length, counting all dictionary entries.
A suffix link shortens the represented string, but it may remove only one character. With the single pattern for , where the exponent means repeated copies of , every nonempty prefix links to . Starting at the final state takes links to reach the root. Only the final state is terminal.
Now make every nonempty prefix a pattern. The trie and its suffix links stay exactly the same, but every nonroot state becomes terminal. Compare the two dictionaries below.
This separates two quantities: how many suffix links exist on the path, and how many distinct patterns occur along it. The second quantity has a stronger bound in terms of the dictionary's total length.
Fix a state and let be the number of terminal vertices among that state and its suffix-link ancestors, excluding the root. Each terminal represents one distinct matching string. Their lengths are positive and different, since suffix links strictly decrease length.
List those lengths increasingly as . The th length is at least . These are lengths of actual dictionary patterns, so their sum cannot exceed . Consequently,
Thus a state has distinct terminal suffixes. The bound is tight: choose . At state , all patterns match, while . The trie has only vertices, so the bound depends on total pattern length, rather than the number of trie vertices.
If all dictionary strings are distinct, a text of length therefore has at most occurrences in total. Duplicate IDs need separate treatment: copies of the one-character pattern give reports at one position, although only one terminal vertex is involved.
The reporting loop from the first lesson also visits nonterminal vertices. Its whole suffix chain can still be long; the square-root bound counts matching terminals, not every step of that loop.
Take . No pattern is a prefix of a longer one: where the shorter pattern has its final , the longer one still has . All patterns end at the final position of , and their total length is .
If no pattern is a proper suffix of another, at most one distinct pattern can end at any position. Two different strings ending there would have different lengths, and the shorter would be a proper suffix of the longer.
Assume the suffix links are known and resolve transitions directly: when the required trie edge is missing, follow suffix links until an edge is available or the root is reached. Here we count the links followed while finding the next search state, without the separate reporting traversal.
Use the depth of the current trie state, meaning its represented string's length, as a running balance. Taking a trie edge consumes one character and increases depth by exactly . Following a suffix link decreases depth by at least . A missing character at the root consumes a character without changing depth.
There are at most increases while reading characters. Starting from depth , we cannot spend more depth than we have gained. Therefore at most nonroot suffix-link steps occur across the whole scan, even if one character triggers a long chain.
This is an amortized bound: an expensive transition is paid for by earlier increases. Reporting has a different behavior. Its temporary vertex walks toward the root while the search state stays in place, so those decreases do not lower the balance used by the next transition.
The maximum is . Let be the number of consumed trie edges and the number of suffix-link steps. If the final state is nonroot, at least one unit of gained depth remains, so .
If the final state is the root, the last character could not have been consumed by a trie edge, which always ends at positive depth. Thus , and again.
Use the dictionary and text . The first character takes the root's edge. Every later character first follows the suffix link back to the root, then takes the same edge. Exactly suffix-link steps occur.
For each nonroot vertex , make its parent. Omit the root's self-link. Every nonroot vertex has one parent, and repeatedly taking parents strictly decreases string length until reaching the root. These edges therefore form a rooted suffix-link tree.
Reuse and the state numbers from the first lesson. The drawing below shows this second tree. Each edge connects a suffix-link parent to its child.
A vertex is an ancestor of in this tree, including , exactly when is a suffix of . Going upward follows all represented suffixes. Equivalently, the subtree of contains precisely the states whose strings end with .
This turns a matching condition into a tree condition: a pattern ending at occurs at the current text position exactly when the current state lies in 's subtree.
Let be the number of pattern IDs stored at . We want to count all IDs ending at the current position when the state is . The current vertex contributes its own IDs; its remaining matching suffixes are those of its suffix-link parent. Set . For a nonroot vertex,
Compute these values once for the tree, then add the current state's value after each text character. This counts overlapping occurrences and duplicate pattern IDs. With transitions available, all values and the text total take time, where is the number of states. A large number of occurrences does not force us to list their positions.
For separate pattern frequencies, start with : the number of text positions whose current state is exactly . The subtree property tells us that the occurrence count at a terminal is the sum of these visits over its subtree:
Initialize each counter with its visit count. After collecting everything below a vertex, add its counter to its suffix-link parent. A traversal that processes children before their parent computes all subtree sums. Processing states in decreasing trie depth is also valid, because every suffix-link parent represents a shorter string.
Follow the accumulation for . Every vertex stays visible while a counter is added upward.
Each visit contributes once to every suffix-link ancestor, exactly the patterns that end at that position. After accumulation, a terminal's counter is therefore its number of occurrences. Duplicate IDs stored at the same terminal receive the same frequency.
The scan and one tree traversal take time after the automaton's transitions are ready. Reading the result for all pattern IDs adds work. The full computation, including the first lesson's automaton construction for letters, takes time and requires extra counting storage.
Suppose no dictionary pattern is a proper prefix of another. For every integer , can a single text position still end distinct patterns with total length ? Construct such a family over the alphabet and justify it. What changes if no pattern is a proper suffix of another?
For a text of length , find the exact maximum number of nonroot suffix-link steps used to resolve transitions, over all nonempty dictionaries and texts. Start at the root, exclude reporting steps, and do not count a root self-loop as a suffix-link step. Give a matching construction.