Unit 5: Naive Pattern Search

I. Orientation: String Matching Fundamentals

Pattern searching asks whether a pattern P of length m occurs inside a text T of length n, and where. It is the backbone of grep, DNA search, plagiarism detectors and compilers. Everything below measures cost in comparisons of characters and in extra space used.

• Text and pattern: T[0..n-1] is searched; P[0..m-1] is sought, with m ≤ n.
• Alignment/window: a candidate start index i in T; the window T[i..i+m-1] is compared against P.
• Match: a shift i where T[i+j] == P[j] for all 0 ≤ j < m.
• Zero-indexing convention: all positions start at 0; a returned index of -1 means "not found".
• Cost vocabulary: preprocessing (work done on P before scanning) versus search (work per window); good algorithms trade the first to shrink the second.

II. The Ubiquitous Naïve Pattern Search Problem

The naïve method slides the pattern one position at a time and compares character by character, with no preprocessing.

A. Method and Principle

• Algorithm: for each start i from 0 to n-m, compare P[0..m-1] against T[i..i+m-1]; on a mismatch break and advance i by 1.
• Pseudocode:
  
  TEXT

  for i in 0 .. n-m:
      j = 0
      while j < m and T[i+j] == P[j]:
          j += 1
      if j == m: report match at i

• Worst case: O(n·m), e.g. T = "aaaaaa", P = "aaab" — every window matches m-1 chars then fails.
• Best/average case: O(n) when first characters rarely match, as in natural-language text.
• Space: O(1); nothing is stored beyond loop indices.

B. Problems Based on Naive Pattern Search

• Counting occurrences: do not break the outer loop after one hit; continue scanning all n-m+1 windows.
• Overlapping matches: searching "aa" in "aaaa" yields hits at 0,1,2; advancing by 1 (not by m) captures overlaps.
• Wildcard ?: treat ? in P as matching any single character inside the inner comparison.
• Anchor with a numeric example: P="abc" in T="ababcab" — mismatches at i=0,1, full match at i=2.

III. KMP Algorithm

Purpose: the Knuth–Morris–Pratt algorithm removes the naïve method's redundant re-comparisons by never moving the text pointer backwards, achieving O(n+m).

A. Longest Prefix Which Is Also a Suffix

The LPS (also called failure function) drives KMP; it records reusable partial matches.

• Definition: lps[k] = length of the longest proper prefix of P[0..k] that is also a suffix of P[0..k]. Proper means shorter than the substring itself.
• Example: for P = "ababaca", lps = [0,0,1,2,3,0,1].
• Construction (O(m)):
  
  TEXT

  lps[0] = 0; len = 0; i = 1
  while i < m:
      if P[i] == P[len]: len++; lps[i] = len; i++
      elif len > 0:      len = lps[len-1]      // fall back
      else:              lps[i] = 0; i++

• Symbols: len = length of current candidate border; the fallback len = lps[len-1] reuses the next-shorter border instead of restarting.

B. Search Using LPS

• Principle: on a mismatch at P[j], shift the pattern so that j = lps[j-1], keeping the text index i fixed.
• Search loop:
  
  TEXT

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

• Guarantee: each of i and j advances a bounded number of times, giving linear time overall.
• Contrast with naïve: the naïve method rescans from i+1; KMP skips the already-matched prefix encoded in lps.

IV. Rabin-Karp Algorithm

Purpose: compare a hash of each window to the pattern's hash, turning most character comparisons into arithmetic; a rolling hash makes each shift O(1).

A. Hashing and the Rolling Update

• Polynomial hash: treat a length-m window as a base-d number modulo a prime q:
  
  TEXT

  hash = (c0·d^(m-1) + c1·d^(m-2) + ... + c_{m-1}) mod q

• Symbols: d = alphabet size (e.g. 256), q = large prime to limit collisions, ci = numeric code of a character.
• Rolling from window i to i+1:
  
  TEXT

  h = ( d·(h - T[i]·h_high) + T[i+m] ) mod q

  
  where h_high = d^(m-1) mod q, precomputed once.
• Verification: a hash match is only a candidate; confirm with a direct character comparison to reject spurious hits (collisions).

B. Complexity and Trade-offs

1. Average / best: O(n+m) when q is large and collisions are rare.
2. Worst: O(n·m) if every window collides (e.g. a poor q), forcing full verification each time.
   • Multi-pattern strength: several patterns of equal length can be sought at once by hashing each and checking membership in a set of hashes.
   • Space: O(1) beyond the hash values.

V. Introduction to Suffix Array

A suffix array is the sorted array of all suffix starting indices of a string, enabling fast repeated queries after one build.

A. Definition and Construction

• Definition: SA holds indices 0..n-1 ordered by the lexicographic value of the suffixes they begin.
• Example: for S = "banana", suffixes sort to a, ana, anana, banana, na, nana, so SA = [5,3,1,0,4,2].
• Build methods: naïve sort of all suffixes is O(n² log n); prefix-doubling with sorting reaches O(n log² n), and specialised algorithms reach O(n).
• LCP array companion: stores the longest common prefix between adjacent SA entries, powering substring and repeat queries.

B. Uses

• Substring test: binary-search a pattern P over SA in O(m log n), since all suffixes sharing a prefix are contiguous.
• Distinct substrings, longest repeated substring: derived directly from SA + LCP.
• Vs. building a suffix tree: the array uses far less memory while answering the same queries slightly slower.

VI. String-Relationship Problems

These reduce recognisable string questions to a single pattern search.

A. Checking if Two Strings Are Rotations of Each Other

• Key trick: B is a rotation of A iff B is a substring of A + A, provided lengths are equal.
• Reason: concatenation exposes every cyclic shift as a contiguous window; e.g. A="abcd", A+A="abcdabcd" contains "cdab".
• Cost: O(n) with KMP on the doubled string; first reject unequal lengths.

B. Check if a String Is Substring of Another String

• Direct approach: run any pattern-search routine; return the first index or -1.
• Empty pattern convention: an empty P is a substring of every T, matching at index 0.
• Library note: built-ins (strstr, str.find, indexOf) implement this; understanding naïve/KMP explains their behaviour on adversarial inputs.

VII. Largest Connected Component on a Grid

Purpose: a 2-D flood-fill problem — treat a grid of cells as a graph and find the biggest region of connected "on" cells.

A. Traversal and Counting

• Model: each cell is a node; edges join adjacent cells (4-directional up/down/left/right, or 8-directional including diagonals — fix which before coding).
• Method: iterate over every cell; on an unvisited "1" cell, run DFS/BFS, marking visited and counting size; track the maximum.
• Pseudocode (DFS core):
  
  TEXT

  def dfs(r,c):
      if out_of_bounds or grid[r][c]!=1 or visited[r][c]: return 0
      visited[r][c] = true
      return 1 + dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)

• Complexity: O(R·C) — each cell is entered once for a grid of R rows and C columns.
• Pitfall: recursion depth can overflow on large grids; an explicit stack or BFS queue avoids this.

VIII. Lexicographical Sorting of Strings

Purpose: order strings as a dictionary does, comparing character codes left to right.

A. Comparison Rule

• Rule: compare position by position; the first differing character decides order by its code point; if one string is a prefix of the other, the shorter comes first ("app" < "apple").
• Case sensitivity: ASCII places all uppercase before lowercase ('Z'=90 < 'a'=97), so "Zebra" < "apple" unless normalised.
• Sorting cost: O(N·L·log N) for N strings of average length L, since each comparison is up to O(L).

B. Practice Variants

• Sort by length then lexicographically: supply a comparator returning length difference first, string order second.
• Custom alphabet: map each character to a rank array and compare ranks (used in "alien dictionary" problems).
• Anchor: ["bb","ba","abc"] sorts to ["abc","ba","bb"].

IX. Splitting a String Into Substrings

Purpose: break a string into tokens by a delimiter or fixed rule, the inverse of concatenation.

A. Techniques

• Delimiter split: scan for the separator (e.g. space or comma), emitting the run between separators; consecutive delimiters may yield empty tokens depending on the chosen policy.
• Fixed-width split: cut every k characters, so "abcdef" with k=2 gives ["ab","cd","ef"].
• Manual two-pointer:
  
  TEXT

  start = 0
  for i in 0..n:
      if i==n or S[i]==delim:
          emit S[start..i-1]; start = i+1

B. Practice Variants

• Palindrome partitioning: split so every piece is a palindrome, explored by recursion/backtracking.
• Balanced substrings: cut wherever a running count (e.g. of L/R) returns to zero.
• Word break: split so each piece belongs to a dictionary, solved with dynamic programming over split points.
• Anchor: "a,b,,c" split on , with empties kept gives ["a","b","","c"].