4. Strings

String Fundamentals

A string is a finite sequence of characters drawn from an alphabet. In most programming languages strings are immutable objects that support operations such as concatenation, slicing, and comparison.

Understanding how strings are stored at the byte level is crucial for performance and correctness, especially when dealing with international text.

Character Encoding

Character encoding maps each abstract character to a specific byte (or byte sequence) value. The choice of encoding influences memory usage, compatibility, and processing speed.

• ASCII: 7‑bit code representing 128 characters (control codes, digits, uppercase/lowercase Latin letters, punctuation).
• Extended ASCII / ISO‑8859‑1: Uses the 8th byte to represent an additional 128 characters, covering Western European languages.
• Unicode: A universal character set aiming to assign a unique code point to every character used in human languages. Unicode is implemented via several encoding forms:
• UTF‑8: Variable‑length encoding using 1 to 4 bytes; backward compatible with ASCII (ASCII characters retain their single‑byte representation).
• UTF‑16: Uses 2 bytes for most characters (BMP) and 4 bytes for supplementary characters via surrogate pairs.
• UTF‑32: Fixed 4‑byte representation for every Unicode code point.

Example: The Euro sign ‘€’ has Unicode code point U+20AC. In UTF‑8 it is encoded as the byte sequence 0xE2 0x82 0xAC.

String Comparison and Equality

Two strings are equal if they have the same length and each corresponding character matches according to the chosen encoding’s collation rules. Locale‑sensitive comparisons may involve case folding, accent removal, or language‑specific ordering.

Pattern Matching Algorithms

Given a text T of length n and a pattern P of length m, the goal is to find all occurrences of P in T. Several algorithms achieve different trade‑offs between preprocessing time, search time, and space usage.

Naive Algorithm

The simplest approach slides the pattern over the text and checks for a match at each position.

Time complexity: O((n‑m+1)·m) in the worst case.

Space complexity: O(1).

Although easy to implement, it becomes inefficient for large texts or patterns with many partial matches.

Knuth‑Morris‑Pratt (KMP) Algorithm

KMP improves performance by preprocessing the pattern to compute the Longest Proper Prefix which is also a Suffix (LPS) array. This information allows the algorithm to skip unnecessary comparisons.

LPS Construction

For each index i (0‑based) in P, LPS[i] stores the length of the longest proper prefix of P[0..i] that is also a suffix of this substring.

Example: Pattern P = "ABABC" yields LPS = [0,0,1,2,0].

Search Phase

During scanning of T, a mismatch at position j in the pattern causes the algorithm to shift the pattern by j‑LPS[j‑1] positions, guaranteeing that no possible match is missed.

Time complexity: O(n + m).

Space complexity: O(m) for the LPS array.

Rabin‑Karp Algorithm

Rabin‑Karp uses a rolling hash to compare the pattern hash with hash values of length‑m windows in the text. When hashes match, a direct character comparison verifies the occurrence.

Hash Function

Given a base d (typically the alphabet size, e.g., 256) and a prime modulus q, the hash of a string S[0..m‑1] is:

h = (d·h + S[i]) mod q

The hash of the next window can be updated in O(1) time using:

h_next = (d·(h_current – T[i]·d^{m‑1}) + T[i+m]) mod q

Example

With d = 256, q = 101, pattern "abc" yields an initial hash that is compared against each text window.

Average case: O(n + m).

Worst case (many spurious hits): O(n·m).

Space: O(1).

Z‑Algorithm

The Z‑algorithm constructs a Z‑array for the concatenated string P + '$' + T (where '$' is a delimiter not appearing in either string). Z[i] equals the length of the longest substring starting at position i that matches the prefix of the concatenated string.

When Z[i] ≥ m at a position corresponding to the text part, an occurrence of the pattern is found.

Example

For T = "aabcaabxaaaz", the Z‑array (starting at index 0) yields Z[2] = 1 (matching “a”) and Z[5] = 3 (matching “aab”).

Time complexity: O(n + m).

Space complexity: O(n + m) for the Z‑array.

Real‑Life Applications

String algorithms are foundational to many software systems. Below are representative use cases that illustrate how the theoretical concepts translate into practical solutions.

Search Engines

Modern search engines build an inverted index mapping each term (string) to the list of documents containing it. Query processing relies on fast string matching to locate candidate documents and then applies ranking functions.

• Indexing: Tokenization, stemming, and case folding produce normalized strings.
• Query matching: Algorithms like KMP or optimized hash‑based lookups retrieve posting lists efficiently.
• Highlighting: Once a match is found, the engine extracts surrounding snippets using substring extraction.

Password Validation

Password policies often require checks for length, presence of uppercase/lowercase letters, digits, and special characters. These checks are commonly expressed as regular expressions, which under the hood are compiled into finite automata that perform linear‑time string scanning.

Example regex: ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[@$!%*?&])[A-Za-z\d@$!%*?&]{8,}$ enforces at least one lowercase, one uppercase, one digit, one special character, and a minimum length of eight.

Text Editors

Features such as find/replace, syntax highlighting, and undo/redo rely heavily on efficient string manipulation.

• Find/Replace: Implemented using KMP or Rabin‑Karp to locate all occurrences of a search pattern; replacement may involve building a new string via a gap buffer or rope data structure.
• Undo/Redo: Typically modeled with two stacks (one for undo actions, one for redo). Each action stores the edited range and the original substring, enabling constant‑time rollback.
• Cursor Movement & Selection: Rope data structures (balanced binary trees of string fragments) provide O(log n) insert/delete and O(log n) access, making large‑scale editing responsive.

Chat Applications

Real‑time messaging platforms need to filter profanity, detect spam, and extract entities (e.g., URLs, hashtags). The Aho‑Corasick automaton—built from a trie of forbidden words—allows simultaneous matching of multiple patterns in linear time relative to the message length.

Workflow:

1. Build a trie from the list of prohibited words.
2. Add failure links (similar to LPS in KMP) to create the automaton.
3. For each incoming message, traverse the automaton character by character; output matches whenever a terminal node is reached.
4. Apply actions such as message rejection, replacement with asterisks, or user notification.

Summary of Complexities

Choosing the appropriate algorithm depends on factors such as pattern length, alphabet size, whether multiple patterns are searched simultaneously, and the acceptable worst‑case behavior.

Further Reading & Exercises

To deepen understanding, implement each algorithm in your preferred language, compare their runtimes on random texts of varying sizes, and experiment with different hash bases and moduli for Rabin‑Karp. Additionally, explore how Unicode normalization (NFC, NFD) affects string matching when dealing with accented characters.