Unit 5: Naive Pattern Search - Subjective Questions

Naïve Pattern Search Problem: Given a text T of length n and a pattern P of length m, the goal is to find all occurrences (starting indices) of P within T.

Working:

• The algorithm slides the pattern over the text one character at a time.
• At each shift position i (from 0 to n-m), it compares characters of the pattern with the corresponding text characters.
• If all m characters match, an occurrence is reported at index i.
• On any mismatch, the pattern is shifted by one position.

Example: T = "AABAACAADAABAABA", P = "AABA".

• Match found at index 0, 9, and 12.

Time Complexity:

• Worst case: (e.g., T = "AAAAA", P = "AAA").
• Best case: .

The algorithm is simple but inefficient for large inputs because it may re-examine characters repeatedly.

KMP Algorithm: An efficient pattern matching algorithm that avoids re-examining previously matched characters by using a precomputed LPS (Longest Prefix Suffix) array.

Key Idea:

• When a mismatch occurs after some matches, KMP uses the LPS array to decide the next position to compare, without moving the text pointer backward.

Steps:

1. Preprocess the pattern to build the LPS array (length of the longest proper prefix which is also a suffix for each position).
2. Search by scanning the text once, using LPS to skip redundant comparisons on mismatch.

Improvement over Naïve:

• Naïve worst case: .
• KMP: because the text pointer never moves backward.

Example LPS for P = "AAAA" is [0, 1, 2, 3].

Thus KMP guarantees linear time, making it far superior for large texts.

LPS Array: For each index i of the pattern, LPS[i] stores the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. A proper prefix excludes the whole string itself.

Construction for P = "ABABCABAB":

Result: LPS = [0, 0, 1, 2, 0, 1, 2, 3, 4].

The LPS array allows the algorithm to skip comparisons on mismatch, achieving time.

Rabin-Karp Algorithm: A pattern matching algorithm that uses hashing to compare the pattern with substrings of the text efficiently.

Working:

1. Compute the hash of the pattern P and the hash of the first window of length m in the text.
2. Slide the window one character at a time, computing a rolling hash for each new window.
3. If the hash of a window matches the pattern's hash, perform a character-by-character verification to confirm a real match (to rule out spurious hits / collisions).

Rolling Hash: Using a base d and prime modulus q:

where .

Role of Hashing:

• Reduces string comparison to integer comparison in per window (on average).
• The rolling hash lets us update the hash in constant time instead of recomputing.

Complexity:

• Average and best: .
• Worst case (many collisions): .

It is especially useful for multiple pattern search and plagiarism detection.

Comparison of KMP and Rabin-Karp:

Key Points:

• KMP is deterministic and never degrades to quadratic time.
• Rabin-Karp shines when searching for many patterns simultaneously since hashes can be compared quickly.
• KMP requires no probabilistic reasoning, while Rabin-Karp depends on a good hash function to avoid collisions.

Suffix Array: A sorted array of all suffixes of a given string. Instead of storing the actual suffixes, it stores the starting indices of the suffixes in lexicographically sorted order.

Example: For S = "banana", the suffixes are:

• 0: banana
• 1: anana
• 2: nana
• 3: ana
• 4: na
• 5: a

Sorted lexicographically: a(5), ana(3), anana(1), banana(0), na(4), nana(2).

Suffix Array = [5, 3, 1, 0, 4, 2].

Construction Methods:

• Naïve: Generate all suffixes and sort them — .
• Efficient: Using prefix-doubling with sorting — or .

Applications:

• Pattern searching using binary search in .
• Finding the longest repeated substring.
• Finding the longest common substring of multiple strings.
• Data compression (used in BWT).

Suffix arrays are a memory-efficient alternative to suffix trees.

Problem: Given two strings s1 and s2, determine if s2 is a rotation of s1 (e.g., "waterbottle" and "erbottlewat").

Key Insight: s2 is a rotation of s1 if and only if:

1. s1 and s2 have the same length, AND
2. s2 is a substring of s1 + s1 (the string concatenated with itself).

Algorithm:

1. If len(s1) != len(s2), return false.
2. Concatenate: temp = s1 + s1.
3. Check whether s2 is a substring of temp (using KMP for efficiency).

Example:

• s1 = "ABCD", s2 = "CDAB".
• temp = "ABCDABCD".
• "CDAB" is present in temp → true.

Complexity:

• Using KMP for substring search: .
• Naïve substring check: .

This elegant trick avoids explicitly generating all rotations.

Problem: Given a 2D grid of cells (e.g., 1s representing land and 0s representing water), find the size of the largest connected component (group of adjacent 1s connected horizontally, vertically, and possibly diagonally).

Approach (DFS/BFS Flood Fill):

1. Iterate over every cell in the grid.
2. When an unvisited cell with value 1 is found, start a DFS/BFS traversal.
3. During traversal, count all connected 1 cells and mark them as visited.
4. Track the maximum count across all components.

Pseudocode (DFS):

function dfs(grid, i, j, visited):
if out of bounds or grid[i][j]==0 or visited[i][j]:
return 0
visited[i][j] = true
count = 1
for each of 8 (or 4) neighbors (di, dj):
count += dfs(grid, i+di, j+dj, visited)
return count

Main Loop:

max = 0
for each cell (i, j):
if grid[i][j]==1 and not visited:
max = maximum(max, dfs(grid, i, j, visited))

Complexity: where R and C are rows and columns, since each cell is visited once.

Connectivity: For 8-directional connectivity, all 8 neighbors are explored; for 4-directional, only up/down/left/right.

Problem: Given a text T (length n) and a pattern P (length m), determine whether P occurs in T.

Naïve Approach:

• Slide the pattern over the text position by position.
• At each position, compare characters until a mismatch or a full match is found.

Pseudocode:

function isSubstring(T, P):
n = length(T)
m = length(P)
for i from 0 to n - m:
j = 0
while j < m and T[i+j] == P[j]:
j = j + 1
if j == m:
return true // pattern found at index i
return false

Complexity Analysis:

• Worst case: — occurs when there are many partial matches (e.g., T="AAAAAB", P="AAAB").
• Best case: — mismatch on the first character at every position.

For large inputs, more efficient algorithms like KMP () or Rabin-Karp are preferred.

Concept: The Longest Proper Prefix which is also a Suffix (LPS) of a string is the longest substring that appears both as a prefix and as a suffix, but is not the entire string itself.

Example: For "abcab":

• Prefixes: a, ab, abc, abca
• Suffixes: b, ab, cab, bcab
• Longest common proper prefix-suffix = "ab" (length 2).

Computation (using KMP's failure function):

1. Initialize LPS[0] = 0 and len = 0.
2. Iterate i from 1 to n-1:
   • If P[i] == P[len]: len++, LPS[i] = len.
   • Else if len != 0: len = LPS[len-1] (fall back).
   • Else: LPS[i] = 0.

Importance:

• Core of the KMP algorithm to skip redundant comparisons.
• Used to find shortest period of a string: period = n - LPS[n-1].
• Helps in problems like string rotation and repeated substring pattern detection.

Complexity: for computation.

Definitions:

• Prefix: Any substring starting from the first character. For "abcd": prefixes are a, ab, abc, abcd.
• Proper Prefix: A prefix that is not the entire string. For "abcd": a, ab, abc.
• Suffix: Any substring ending at the last character. For "abcd": d, cd, bcd, abcd.
• Proper Suffix: A suffix that is not the entire string. For "abcd": d, cd, bcd.
• Border: A string that is both a proper prefix and a proper suffix. For "abcabc": abc is a border (also "" trivially).

Comparison Table:

Example: For "aabaa":

• Proper prefixes: a, aa, aab, aaba.
• Proper suffixes: a, aa, baa, abaa.
• Borders: a, aa → longest border = aa.

Borders are precisely what the LPS array captures in KMP.

Lexicographical Sorting: Arranging strings in dictionary order, comparing them character by character based on their character codes (e.g., ASCII/Unicode).

Rules:

1. Compare characters at each position from left to right.
2. The string with the smaller character at the first differing position comes first.
3. If one string is a prefix of another, the shorter string comes first (e.g., "app" < "apple").

Example:
Input: ["banana", "apple", "apricot", "app"]

Sorted lexicographically: ["app", "apple", "apricot", "banana"].

Difference from Numerical Sorting:

Key Note: Uppercase letters (A-Z: 65–90) come before lowercase (a-z: 97–122) in ASCII, so "Zebra" < "apple" in strict ASCII lexicographical order.

Complexity: Sorting k strings of max length L takes .

Problem: Given a string and a delimiter, break it into a list of substrings (tokens).

Approaches:

1. Iterative scan:

• Traverse the string, accumulate characters into a buffer until the delimiter is found, then push the buffer as a token.

function split(s, delim):
result = []
token = ""
for ch in s:
if ch == delim:
result.add(token)
token = ""
else:
token = token + ch
result.add(token) // last token
return result

2. Built-in library functions:

• Python: s.split(",")
• Java: s.split(",") (regex-based)
• C++: using stringstream with getline.

Example: "a,b,c,d" split by , → ["a", "b", "c", "d"].

Edge Cases:

• Consecutive delimiters produce empty tokens ("a,,b" → ["a", "", "b"]).
• Leading/trailing delimiters produce empty tokens at the ends.

Complexity: where n is the length of the string.

Applications: Parsing CSV data, tokenizing input, processing command-line arguments.

Naïve Algorithm Recap: For text of length n and pattern of length m, we try each of the n - m + 1 shift positions and compare up to m characters at each.

Worst Case: .

• Occurs when at each shift, almost all characters match before a final mismatch.
• Example: T = "AAAAAAAAAB" (n A's), P = "AAAB". Nearly m comparisons happen at each of the n-m+1 positions.

Best Case: .

• Occurs when the first character mismatches at nearly every shift position.
• Example: T = "ABCDEFG", P = "XYZ". Only 1 comparison per shift → about n comparisons total.

Average Case: for random text over a reasonably large alphabet.

• On average, mismatches occur quickly, so the expected number of comparisons per shift is a small constant.

Summary Table:

Space Complexity: — no extra data structures used.

Building the LPS array for P = "AABAACAABAA":

Result: LPS = [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5].

How KMP Uses LPS on Mismatch:

• Suppose we matched up to pattern index j and text index i, then T[i] != P[j].
• Instead of restarting j = 0, KMP sets j = LPS[j-1].
• This reuses the already-matched border, so the text pointer i never moves backward.

Example: If a mismatch occurs at j = 9 (after matching "AABAACAAB"), we set j = LPS[8] = 3, meaning we continue comparing from pattern index 3 without rescanning matched text.

This is what gives KMP its guarantee.

Rolling Hash: A technique to compute the hash of the next window in constant time from the current window's hash, avoiding recomputation from scratch.

Formula: For a window sliding right by one character, with base d and modulus q:

where .

• We remove the leftmost character's contribution and add the new rightmost character.

Spurious Hits (False Positives):

• Two different strings can produce the same hash value (a hash collision).
• When hashes match, Rabin-Karp verifies with a character-by-character comparison to confirm a real match.
• A hash match that is not a real match is called a spurious hit.

Why a Prime Modulus?

• Using a large prime q minimizes the probability of collisions by distributing hash values more uniformly.
• It reduces clustering of hash values, keeping spurious hits rare.
• This keeps the average time complexity close to .

Trade-off: A larger q reduces collisions but must fit within integer limits to avoid overflow.

Pattern Search Using Suffix Array:

Since a suffix array stores the starting indices of all suffixes in sorted order, any pattern that occurs in the text is a prefix of some suffix. Because the suffixes are sorted, all occurrences of a pattern appear in a contiguous range of the suffix array.

Algorithm (Binary Search):

1. Build the suffix array of the text T (length n) — one-time preprocessing.
2. To search a pattern P (length m), perform binary search over the suffix array.
3. At each step, compare P with the suffix at the middle index (comparison takes up to ).
4. Narrow the search range to find the first and last occurrence.

Example: For T = "banana", suffix array = [5, 3, 1, 0, 4, 2]. To search "ana", binary search locates the suffixes "ana" (index 3) and "anana" (index 1).

Time Complexity:

• Each binary search step does an comparison, with steps.
• Search time: .
• Preprocessing (build): with efficient methods.

Advantage: Once built, multiple pattern queries are answered quickly, making suffix arrays ideal for repeated searches.

Concept: The period of a string is the smallest length p such that the string is formed by repeating a block of length p. The LPS array (from KMP) directly gives this.

Formula:

• If n % period == 0, the string is a perfect repetition of a block of length period.

Algorithm:

function shortestPeriod(s):
n = length(s)
lps = computeLPS(s)
period = n - lps[n-1]
if n % period == 0:
return period // string is repetition of a block
else:
return n // no smaller repeating period

Illustration for "abcabcabc" (n = 9):

• Compute LPS: [0, 0, 0, 1, 2, 3, 4, 5, 6].
• LPS[8] = 6.
• period = 9 - 6 = 3.
• Since 9 % 3 == 0, the shortest period is 3, and the repeating block is "abc".

Complexity: — dominated by LPS computation.

Application: Detecting repeated patterns, string compression, and the 'Repeated Substring Pattern' problem.

Common Problems Solved with Naïve Pattern Search:

• Substring check: Determining whether one string occurs in another.
• Counting occurrences: Finding the number of times a pattern appears in a text.
• Finding all indices: Listing all starting positions of a pattern.
• Anagram/rotation checks: Combined with concatenation tricks.
• Simple find-and-replace: Locating positions before replacement.
• Wildcard matching (basic): Extending naïve comparison to handle ? and *.

Why Naïve Search Is Still Useful:

• Simplicity: Easy to implement and understand — fewer bugs.
• Small inputs: For short texts/patterns, the overhead of preprocessing (KMP/Rabin-Karp) is not worth it.
• Good average performance: On random text over a large alphabet, mismatches occur early, giving near behavior.
• No extra space: Uses auxiliary space, unlike KMP's LPS array.
• Baseline / teaching: Serves as a foundation for understanding advanced algorithms.

Limitation: Its worst case makes it unsuitable for very large texts with repetitive patterns, where KMP or Rabin-Karp should be used.

Pseudocode for Lexicographical Sorting:

function lexSort(arr):
n = length(arr)
for i from 0 to n-2:
for j from 0 to n-2-i:
if compare(arr[j], arr[j+1]) > 0:
swap(arr[j], arr[j+1])
return arr

function compare(a, b):
k = min(length(a), length(b))
for i from 0 to k-1:
if a[i] != b[i]:
return a[i] - b[i] // char code difference
return length(a) - length(b) // shorter comes first

(In practice, use built-in sort with a string comparator for performance.)

Practice Problem — 'Largest Number from Strings':

• Given a list of numeric strings, arrange them to form the largest number.
• Trick: Sort using a custom comparator: for two strings a and b, place a before b if a+b > b+a (comparing concatenations lexicographically).
• Example: ["3", "30", "34", "5", "9"] → "9534330".

Why Lexicographical Ordering Matters:

• It provides a consistent, total ordering for strings, essential in dictionaries, autocomplete, ranking, and comparator-based problems where numeric comparison alone fails.

Complexity: with an efficient sort, where L is the maximum string length.