Build a Dynamic Exact-Suffix Search Index

Dynamic Exact-Suffix Search Index

Design a data structure that maintains a dynamic collection of strings and supports efficient suffix lookups. The data structure must handle interleaved insertions and queries, where a query determines if any string currently in the collection ends with a specified exact, case-sensitive suffix.

Implement the SuffixIndex class:

• SuffixIndex(): Initializes the index data structure.
• void insert(String word): Inserts word into the collection.
• boolean has_suffix(String suffix): Returns true if at least one word inserted into the collection ends with suffix, and false otherwise.

Interface

class SuffixIndex:
    def __init__(self):
        pass

    def insert(self, word: str) -> None:
        pass

    def has_suffix(self, suffix: str) -> bool:
        pass

Examples

index = SuffixIndex()
index.insert("surveillance")
index.insert("guidance")
index.insert("reconnaissance")

index.has_suffix("ance")    # Returns True ("guidance", "reconnaissance")
index.has_suffix("lance")   # Returns True ("surveillance")
index.has_suffix("surveil") # Returns False ("surveil" is a prefix, not a suffix)
index.has_suffix("e")       # Returns True (all three words end in "e")
index.has_suffix("drone")   # Returns False

Constraints

• 1 <= word.length, suffix.length <= 2,000
• word and suffix consist of printable ASCII characters and are case-sensitive.
• At most 100,000 total calls to insert and has_suffix combined.
• Total length of all inserted words does not exceed 1,000,000 characters.

Edge Cases

• A word is considered a suffix of itself (e.g., after inserting "target", has_suffix("target") must return true).
• Querying before any words are inserted should safely return false.
• Case sensitivity: "Radar" does not match suffix "radar".