String Data Structures Guide

Data Structures Data Structures 8 min read 1544 words Beginner ExcellentWiki Editorial Team

String algorithms are the backbone of text processing, search engines, and bioinformatics.

String Matching Basics

Naive Approach

Check every position for a match:

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            yield i  # Match found at position i

Time: O(n×m). Fine for small strings. Terrible for large ones.

KMP (Knuth-Morris-Pratt)

Avoids re-checking characters by using a prefix function.

How it Works

Build a “failure function” (LPS — Longest Proper Prefix that is also Suffix):

def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    j = 0  # Length of previous LPS
    
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
    return lps

Pattern: "ABABAC"
LPS:     [0, 0, 1, 2, 3, 0]

Search

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)
    j = 0  # Pattern index
    
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]  # Backtrack using LPS
        if text[i] == pattern[j]:
            j += 1
            if j == m:
                yield i - m + 1  # Match
                j = lps[j - 1]

Time: O(n + m). No backtracking in the text.

Rabin-Karp

Uses hashing to compare substrings in O(1).

Rolling Hash

def rabin_karp(text, pattern, base=256, mod=1000003):
    n, m = len(text), len(pattern)
    if m > n: return
    
    h_pattern = 0  # Hash of pattern
    h_window = 0   # Hash of current window
    power = pow(base, m - 1, mod)  # base^(m-1) mod mod
    
    for i in range(m):
        h_pattern = (h_pattern * base + ord(pattern[i])) % mod
        h_window = (h_window * base + ord(text[i])) % mod
    
    for i in range(n - m + 1):
        if h_pattern == h_window:
            if text[i:i+m] == pattern:
                yield i
        
        if i < n - m:
            # Slide window: remove left char, add right char
            h_window = (h_window - ord(text[i]) * power) % mod
            h_window = (h_window * base + ord(text[i + m])) % mod

Time: O(n + m) average, O(n×m) worst (hash collisions).

Space: O(1).

Best for: Multi-pattern search (one hash lookup per pattern).

Trie (Prefix Tree)

A tree where each node represents a character.

           root
         /  |   \
        a   b    c
       /    |    |
      n     e    a
     / \    |    |
    t  d    l    t

Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Time: O(L) per operation (L = string length).

Space: O(total characters in all strings).

Use cases: Autocomplete, spell check, IP routing.

Aho-Corasick

Multi-pattern string matching. Builds a Trie with failure links (like KMP for multiple patterns).

Patterns: ["he", "she", "his", "hers"]

Trie with failure links:
     root
    /    \
   h      s
  / \     |
 e   i    h
 |   |    |
 r   s    e
 |        |
 s        ← failure links shown as →

Complexity

Step	Time
Build Trie	O(total pattern length)
Build failure links	O(total pattern length)
Search	O(n + matches)

Implementation

from collections import deque

class AhoCorasick:
    def __init__(self):
        self.trie = [{}]
        self.output = [[]]
        self.fail = [0]
    
    def add(self, word, index):
        node = 0
        for ch in word:
            if ch not in self.trie[node]:
                self.trie[node][ch] = len(self.trie)
                self.trie.append({})
                self.output.append([])
                self.fail.append(0)
            node = self.trie[node][ch]
        self.output[node].append(index)
    
    def build(self):
        q = deque()
        for ch, next_node in self.trie[0].items():
            q.append(next_node)
            self.fail[next_node] = 0
        
        while q:
            r = q.popleft()
            for ch, u in self.trie[r].items():
                q.append(u)
                v = self.fail[r]
                while v and ch not in self.trie[v]:
                    v = self.fail[v]
                self.fail[u] = self.trie[v].get(ch, 0)
                self.output[u].extend(self.output[self.fail[u]])
    
    def search(self, text):
        node = 0
        for i, ch in enumerate(text):
            while node and ch not in self.trie[node]:
                node = self.fail[node]
            node = self.trie[node].get(ch, 0)
            for pattern_index in self.output[node]:
                yield i, pattern_index

Suffix Tree

A compressed trie of all suffixes of a string.

Example: “banana”

Suffixes: "banana", "anana", "nana", "ana", "na", "a"

Suffix tree (simplified):
            root
          /   |   \
        $a    $    banana$
        |    / \
       na$  na  na$na$
           / \    |
          $  na$  na$
                 / \
                $  na$

Ukkonen’s Algorithm

Builds the suffix tree in O(n) time.

Suffix Array

A sorted array of all suffixes of a string.

String: "banana"
Suffixes:
  banana  (0)  →  sorted:
  anana   (1)      a        (5)
  nana    (2)      ana      (3)
  ana     (3)      anana    (1)
  na      (4)      banana   (0)
  a       (5)      na       (4)
                   nana     (2)

Suffix Array: [5, 3, 1, 0, 4, 2]

LCP Array (Longest Common Prefix)

Suffix array: [5, 3, 1, 0, 4, 2]
Corresponding suffixes:
  "a"                                    LCP[0] = 0
  "ana"         lcp("a", "ana") = 1      LCP[1] = 1
  "anana"       lcp("ana", "anana") = 3  LCP[2] = 3
  "banana"      lcp("anana", "banana") = 0 LCP[3] = 0
  "na"          lcp("banana", "na") = 0  LCP[4] = 0
  "nana"        lcp("na", "nana") = 2    LCP[5] = 2

Applications:

Find longest repeated substring: max LCP value
Pattern search: binary search on suffix array
String matching in O(m + log n)

String Algorithm Comparison

Algorithm	Time (search)	Space	Patterns	Use Case
Naive	O(n×m)	O(1)	Single	Short strings
KMP	O(n+m)	O(m)	Single	Text editing, search
Rabin-Karp	O(n+m) avg	O(1)	Multi	Plagiarism detection
Boyer-Moore	O(n/m) best, O(n×m) worst	O(chars)	Single	Practical fastest
Trie	O(m) per lookup	O(total chars)	Multiple	Autocomplete, dictionary
Aho-Corasick	O(n+matches)	O(total patterns)	Many	Virus scanning, filtering
Suffix tree	O(m)	O(n)	Single (many queries)	Genome analysis
Suffix array	O(m + log n)	O(n)	Single (many queries)	Text indexing

Choose the right string algorithm — your search engine, genome aligner, or text editor depends on it.

Advanced String Data Structures

Suffix Trees

A suffix tree is a compressed trie containing all suffixes of a given text, constructed in O(n) time using Ukkonen’s algorithm. The suffix tree enables solutions to many string problems in linear time: exact string matching, longest repeated substring, longest common substring of two strings, and the number of distinct substrings. Each leaf corresponds to a suffix, and the path from root to leaf spells out that suffix. Internal nodes represent repeated substrings. The suffix tree requires considerable memory — approximately 10-20 bytes per character — making suffix arrays (which store only the sorted suffix indices) a more memory-efficient alternative. The suffix array combined with the LCP (Longest Common Prefix) array provides equivalent functionality with less memory overhead and simpler construction.

Aho-Corasick Algorithm

The Aho-Corasick algorithm builds a finite state machine from a set of patterns in O(m) time where m is the total length of all patterns, then scans the input text in O(n + total_matches) time. The automaton consists of a trie of patterns augmented with failure links — when a character mismatch occurs at a node, the failure link points to the node representing the longest proper suffix of the current prefix. This enables simultaneous matching of all patterns in a single pass through the text. Applications include virus signature detection, sensitive data redaction, and keyword filtering in search engines. The algorithm is particularly efficient when the pattern set is large but the patterns themselves are relatively short.

Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) is the foundation of bzip2 compression and modern DNA sequence aligners like Bowtie and BWA. The BWT rearranges characters of a string so that identical characters tend to cluster together, enabling efficient run-length encoding. The transform is reversible without loss of data. In bioinformatics, the FM-index (a compressed full-text substring index based on the BWT) enables pattern matching in O(m) time with extremely small memory footprints — a human genome can be indexed in 2-3 GB of RAM. The backward search algorithm on the FM-index counts and locates occurrences of a pattern using only the BWT and auxiliary rank data structures.

Frequently Asked Questions

What is the difference between a trie and a suffix tree? A trie stores a set of strings by prefix — each node represents a prefix common to multiple strings. A suffix tree stores all suffixes of a single string in a compressed trie — it merges nodes with single children into edges labeled with strings. Suffix trees enable problems like longest repeated substring that are not easily solved with tries.

How do I choose between hash-based and trie-based string matching? Hash-based matching (Rabin-Karp) is simple and fast for single pattern search. Trie-based matching (Aho-Corasick) is superior for multi-pattern search because it finds all occurrences of all patterns in a single pass. Hash tables consume memory proportional to the number of patterns, while tries share common prefixes, using less memory for overlapping patterns.

What is the space complexity of string data structures? A trie using arrays has O(ALPHABET_SIZE × nodes) memory, which can be large for 256-byte alphabets. Hash-map-based tries reduce memory but add overhead per node. Suffix trees require O(n) memory but with a high constant factor (10-20× the text size). Suffix arrays require 4n bytes for the array plus LCP array. The FM-index provides substring search with sub-linear space.

Tries Guide — Trees and Graphs Guide — Sorting Algorithms Guide

Share this article

X LinkedIn Facebook Email