Unit 2: String Matching Algorithms and Computational Geometry

I. Orientation

String matching locates occurrences of a pattern within text, while computational geometry designs algorithms for objects such as points, line segments, and polygons. Both areas illustrate how preprocessing, data organization, and divide-and-conquer can improve on exhaustive search.

• Input conventions:
  • A text (T[0\ldots n-1]) has length (n).
  • A pattern (P[0\ldots m-1]) has length (m), normally with (m\le n).
  • A match at shift (s) satisfies (T[s+j]=P[j]) for every (0\le j<m).
  • Geometric points are usually represented as Cartesian pairs (p=(x,y)).
• Performance measures:
  • Time complexity counts comparisons, arithmetic operations, or geometric predicates.
  • Space complexity includes preprocessing tables, indexes, recursion, and temporary arrays.
  • Output-sensitive algorithms may depend on output size, such as the number (h) of hull vertices.
• Core strategies:
  • Exhaustive search: inspect all candidate positions or pairs.
  • Preprocessing: extract pattern structure before searching.
  • Hashing: compare compact fingerprints before checking characters.
  • Divide-and-conquer: solve smaller geometric instances and combine them.
• Accuracy conventions:
  • String algorithms discussed here find exact, not approximate, matches.
  • Geometric predicates should avoid unreliable floating-point slope comparisons where cross products suffice.

II. Sequential Search — Linear Scanning of Unordered Data

A. Sequential Search

Sequential search examines elements one at a time until it finds the target or reaches the end.

• Input and output: Given array (A[0\ldots n-1]) and key (x), return an index (i) satisfying (A[i]=x), or (-1) if no such index exists.
• Procedure:

SEQUENTIAL-SEARCH(A, n, x)
    for i = 0 to n - 1
        if A[i] = x
            return i
    return -1

• Correctness invariant: Before iteration (i), none of (A[0],\ldots,A[i-1]) equals (x); therefore, returning (i) is valid, and finishing proves absence.
• Complexity:
  • Best case: (\Theta(1)), when (A[0]=x).
  • Worst case: (\Theta(n)), when (x) is absent or last.
  • Extra space: (\Theta(1)).
• Use and limitation: It works without sorting and suits small or frequently changing collections, but repeated searches over static data favor sorting, hashing, or indexing.

III. Brute-Force String Matching — Testing Every Alignment

A. Brute-Force String Matching

Brute-force string matching aligns the pattern at every feasible text position and directly compares corresponding characters.

• Candidate shifts: The possible starting positions are (s=0,1,\ldots,n-m), giving (n-m+1) alignments.
• Comparison rule: At shift (s), compare (P[j]) with (T[s+j]) from (j=0) onward; reject the shift at the first mismatch.
• Operation count: At most (m(n-m+1)) character comparisons occur, so worst-case time is (O(nm)).
• Worst-case structure: Repetition delays mismatches; for (T=\texttt{AAAAAA}) and (P=\texttt{AAA}), every alignment requires all three comparisons.
• Properties: The method uses (O(1)) auxiliary space, needs no preprocessing, and works with any alphabet supporting equality tests.
• Trade-off: It is simple and effective for short patterns, but it forgets information gained from previous comparisons.

IV. Naive Pattern Matching — Direct Exact-Match Procedure

A. Naive Pattern Matching

Naive pattern matching is the standard procedural realization of the brute-force alignment strategy and can report every occurrence, including overlaps.

• Algorithm:

NAIVE-MATCH(T, P, n, m)
    for s = 0 to n - m
        j = 0
        while j < m and T[s + j] = P[j]
            j = j + 1
        if j = m
            report s

• Correctness: A shift is reported only after all (m) equalities succeed; every feasible shift is examined, so no occurrence is omitted.
• Overlap handling: For (T=\texttt{ABABA}) and (P=\texttt{ABA}), the algorithm reports shifts (0) and (2).
• Complexity:
  • Worst case: (O((n-m+1)m)=O(nm)).
  • Favorable inputs: approximately (O(n)) when most alignments fail on the first comparison.
  • Space: (O(1)), excluding reported positions.
• Distinction: “Brute force” names the general exhaustive design principle; “naive pattern matching” names its direct string-search algorithm.

V. Rabin-Karp Algorithm — Matching Through Rolling Hashes

A. Rabin-Karp Algorithm

Rabin-Karp compares numeric fingerprints of the pattern and each length-(m) text window, verifying characters only when hashes agree.

• Hash definition: For alphabet radix (d) and prime modulus (q),

H(S) = (S[0]d^(m-1) + S[1]d^(m-2) + ... + S[m-1]) mod q

Here (S[i]) is a numeric character code, (m) is window length, and (H(S)) is its hash.

• Rolling update: If (t_s) hashes (T[s\ldots s+m-1]), then

t_(s+1) = (d(t_s - T[s]h) + T[s+m]) mod q
h = d^(m-1) mod q

This removes the outgoing character and appends the incoming one in (O(1)) time.

• Spurious hits: Equal hashes do not guarantee equal strings because collisions are possible; therefore, a character-by-character check follows each hash match.
• Complexity: Preprocessing takes (O(m)); expected search time is (O(n+m)), but repeated collisions can produce (O(nm)) worst-case time.
• Strength: One rolling pass can efficiently search for several equal-length patterns by storing their hashes.
• Practical control: A large prime (q), or two independent moduli, reduces collision probability without eliminating the need for verification.

VI. Knuth-Morris-Pratt Algorithm — Reusing Prefix Information

A. Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt (KMP) avoids rechecking text characters by preprocessing how the pattern overlaps with itself.

• LPS definition: (\operatorname{LPS}[i]) is the length of the longest proper prefix of (P[0\ldots i]) that is also its suffix; “proper” excludes the whole substring.
• Example table: For (P=\texttt{ABABC}), the LPS values are ([0,0,1,2,0]), because (\texttt{AB}) is both prefix and suffix of (\texttt{ABAB}).
• Mismatch rule: If (T[i]\ne P[j]) after (j>0) matched characters, set (j=\operatorname{LPS}[j-1]) without decreasing (i).
• Search procedure:

while i < n
    if T[i] = P[j]: i++, j++
    if j = m: report i - m; j = LPS[j - 1]
    else if i < n and T[i] != P[j]
        if j > 0: j = LPS[j - 1]
        else: i++

• Complexity: LPS construction costs (O(m)); searching costs (O(n)); total time is (O(n+m)) with (O(m)) auxiliary space.
• Guarantee: Unlike Rabin-Karp, KMP has deterministic linear worst-case time and uses no hash collision checks.

VII. Data Structures for String Processing — Organizing Characters and Prefixes

A. Data Structures for String Processing

String-processing structures trade construction time and memory for faster lookup, prefix search, or repeated pattern queries.

• Arrays and strings: Contiguous storage gives (O(1)) indexed character access, which supports naive matching, hashing, and KMP.
• Hash tables: Whole strings or fixed-length fingerprints can be stored with expected (O(1)) lookup, though collisions require resolution and equality checks.
• Prefix-based structures: Tries organize keys character by character, making operation time depend mainly on key length rather than the number of stored strings.
• Suffix structures:
  • A suffix tree stores all suffixes in compressed-trie form and supports pattern search in (O(m)) after construction.
  • A suffix array stores sorted suffix starting positions more compactly and supports binary-search-based matching, commonly in (O(m\log n)).
• Selection criteria: Alphabet size, memory budget, update frequency, number of searches, and required query type determine the suitable representation.

VIII. Trie (Prefix Tree) — Character-by-Character Dictionary Index

A. Trie (Prefix Tree)

A trie is a rooted tree in which each edge represents a character and each root-to-node path represents a prefix.

• Node contents: A node stores child references and usually an end-of-word marker to distinguish keys such as (\texttt{car}) from the prefix of (\texttt{cart}).
• Operations:
  • Insert: follow or create one edge per character.
  • Search: follow all characters and confirm the terminal marker.
  • Prefix query: follow the prefix; all descendant terminal nodes represent completions.
• Complexity: Insertion and search take (O(L)), where (L) is the key length; this is independent of the number of stored keys.
• Example structure: Keys (\texttt{to}), (\texttt{tea}), and (\texttt{ten}) share the initial edge (\texttt{t}), while (\texttt{tea}) and (\texttt{ten}) additionally share (\texttt{te}).
• Representation choices: Child arrays provide fast access for small fixed alphabets; maps save space for sparse or large alphabets.
• Limitation: Many nodes and pointers can consume substantial memory; path-compressed radix trees reduce chains of single-child nodes.

IX. Closest-Pair Problem — Minimum Distance Among Points

A. Closest-Pair Problem

The closest-pair problem finds two distinct points whose Euclidean distance is minimum among (n) planar points.

• Distance formula: For (p=(x_p,y_p)) and (q=(x_q,y_q)),

dist(p,q) = sqrt((x_p - x_q)^2 + (y_p - y_q)^2)

Squared distances may be compared to avoid repeated square roots.

• Brute force: Testing all (\binom n2=n(n-1)/2) pairs takes (\Theta(n^2)) time and (O(1)) extra space.
• Divide-and-conquer:
  • Sort points by (x)-coordinate.
  • Divide at the median and recursively find left and right minima.
  • Let (\delta) be the smaller recursive distance.
  • Examine points within horizontal distance (\delta) of the dividing line.
• Strip property: With strip points ordered by (y), each point needs comparison with only a constant number of subsequent points—commonly bounded by seven—because of planar packing.
• Complexity: Maintaining (y)-sorted lists gives the recurrence (T(n)=2T(n/2)+O(n)), hence (T(n)=O(n\log n)).
• Applications: Uses include collision detection, geographic analysis, clustering, and identifying duplicate or near-duplicate coordinates.

X. Convex Hull — Smallest Convex Boundary

A. Convex Hull

The convex hull of a point set is the smallest convex set containing all points, represented in two dimensions by its boundary vertices in cyclic order.

• Geometric interpretation: It is the polygon formed by stretching an elastic band around the outermost points; interior points do not appear as hull vertices.
• Orientation predicate: For (a=(x_a,y_a)), (b=(x_b,y_b)), and (c=(x_c,y_c)),

cross(a,b,c) =
(b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)

A positive value indicates a counterclockwise turn, negative indicates clockwise, and zero indicates collinearity.

• Graham scan: Choose the lowest point, sort others by polar angle, and maintain a stack; pop while the latest three points fail to make the required counterclockwise turn.
• Monotone chain: Sort points lexicographically by ((x,y)), then construct lower and upper hulls using the same cross-product test.
• Complexity: Sorting dominates both methods, giving (O(n\log n)) time; stack construction itself is (O(n)), and storage is (O(n)).
• Degenerate cases: Duplicate points should be removed, and an explicit convention must decide whether collinear boundary points are retained or only extreme endpoints.
• Applications: Convex hulls support shape analysis, collision detection, GIS boundaries, image processing, and preprocessing for geometric optimization.