> ## Documentation Index
> Fetch the complete documentation index at: https://resq-dependabot-github-actions-github-actions-478e18be3d.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Trie

<a id="resq_dsa.trie" />

# resq\_dsa.trie

Trie data structure and string matching algorithms.

This module provides a prefix tree (Trie) implementation for efficient
string storage and retrieval, along with the Rabin-Karp string matching
algorithm for pattern search.

Classes:
Trie: Prefix tree for word storage and prefix-based retrieval.

Functions:
rabin\_karp: Find all occurrences of a pattern in text using rolling hash.

<a id="resq_dsa.trie.Trie" />

## Trie Objects

```python theme={null}
class Trie()
```

Prefix tree for efficient string storage and retrieval.

A Trie organizes strings by common prefixes, enabling fast lookup
for word existence and autocomplete-style prefix searches.

**Attributes**:

* `_root` - The root node of the Trie.

**Example**:

> > > trie = Trie()
> > > trie.insert("hello")
> > > trie.insert("help")
> > > trie.search("hello")
> > > True
> > > trie.starts\_with("hel")
> > > \['hello', 'help']

<a id="resq_dsa.trie.Trie.__init__" />

#### Trie.\_\_init\_\_

```python theme={null}
def __init__() -> None
```

Initialize an empty Trie.

<a id="resq_dsa.trie.Trie.insert" />

#### Trie.insert

```python theme={null}
def insert(word: str) -> None
```

Insert a word into the Trie.

**Arguments**:

* `word` - The word to insert.

**Example**:

> > > trie = Trie()
> > > trie.insert("python")

<a id="resq_dsa.trie.Trie.search" />

#### Trie.search

```python theme={null}
def search(word: str) -> bool
```

Check if a word exists in the Trie.

**Arguments**:

* `word` - The word to search for.

**Returns**:

True if the word exists, False otherwise.

**Example**:

> > > trie = Trie()
> > > trie.insert("test")
> > > trie.search("test")
> > > True
> > > trie.search("tes")
> > > False

<a id="resq_dsa.trie.Trie.starts_with" />

#### Trie.starts\_with

```python theme={null}
def starts_with(prefix: str) -> list[str]
```

Find all words in the Trie that start with a given prefix.

**Arguments**:

* `prefix` - The prefix to search for.

**Returns**:

List of all words that have the given prefix.

**Example**:

> > > trie = Trie()
> > > trie.insert("hello")
> > > trie.insert("help")
> > > trie.insert("hero")
> > > trie.starts\_with("he")
> > > \['hello', 'help', 'hero']

<a id="resq_dsa.trie.rabin_karp" />

#### rabin\_karp

```python theme={null}
def rabin_karp(text: str, pattern: str) -> list[int]
```

Find all starting positions where pattern occurs in text.

Uses the Rabin-Karp algorithm with rolling hash for efficient string
matching. Returns all positions where the pattern matches.

**Arguments**:

* `text` - The text to search in.
* `pattern` - The pattern to search for.

**Returns**:

List of starting indices where pattern occurs in text.

**Example**:

> > > rabin\_karp("ABABDABACDABABCABAB", "ABABCABAB")
> > > \[10]
> > > rabin\_karp("hello world", "wor")
> > > \[6]
> > > rabin\_karp("test", "xyz")
> > > \[]