Packet Suffix Variety
Preview mode. Log in to edit, run, submit, and save progress.
Packet Suffix Variety
A packet recorder receives a lowercase stream and wants to know how many different contiguous fragments can appear inside it. A fragment is any non-empty substring. If the same substring appears multiple times at different positions, it is counted only once. The answer is the number of distinct fragments, not the number of occurrences. Input Format: You are given a string s. Output Format: Return the number of distinct non-empty substrings of s.
Examples
s = "ababa"
9
Explanation: The distinct substrings are ["a", "b", "ab", "ba", "aba", "bab", "abab", "baba", "ababa"]. Count = 9, so the output is 9.
Approach hint
A trie or suffix automaton is ideal for very large limits.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.