Pattern Matching Algorithms in C

Naive (Brute Force) Algorithm

1. What is the time complexity of the naive string matching algorithm?

A) O(n)

B) O(n log n)

C) O(nm)

D) O(n^2)

Answer: C) O(nm)

The naive algorithm has O(nm) complexity where n is text length and m is pattern length, as it checks all possible positions.

2. What is the main disadvantage of the brute force approach?

A) High space complexity

B) Doesn't work with Unicode

C) No preprocessing phase

D) Rechecks characters unnecessarily

Answer: D) Rechecks characters unnecessarily

The brute force algorithm doesn't use information from previous matches, leading to redundant comparisons.

Knuth-Morris-Pratt (KMP) Algorithm

3. What is the key idea behind the KMP algorithm?

A) Hashing the pattern

B) Using a finite automaton

C) Longest prefix suffix array

D) Binary search approach

Answer: C) Longest prefix suffix array

KMP uses the LPS array to avoid re-checking characters by leveraging information about the pattern's structure.

4. What is the time complexity of KMP algorithm?

A) O(n)

B) O(n + m)

C) O(n log m)

D) O(nm)

Answer: B) O(n + m)

KMP has linear time complexity - O(m) for preprocessing and O(n) for searching.

Boyer-Moore Algorithm

5. What are the two heuristics used in Boyer-Moore algorithm?

A) Bad character and good suffix

B) Prefix and suffix matching

C) Hashing and binary search

D) Knuth's optimization

Answer: A) Bad character and good suffix

Boyer-Moore uses both bad character rule (rightmost mismatch) and good suffix rule (matching suffix) to skip alignments.

6. In practice, what is Boyer-Moore's average case complexity?

A) O(n/m)

B) O(n + m)

C) O(n log m)

D) O(n)

Answer: A) O(n/m)

With good heuristics, Boyer-Moore often skips many characters, achieving sub-linear performance in practice.

Rabin-Karp Algorithm

7. What is the key technique used in Rabin-Karp algorithm?

A) Dynamic programming

B) Hashing

C) Divide and conquer

D) Backtracking

Answer: B) Hashing

Rabin-Karp uses hashing to compare the pattern with text substrings, only doing full comparisons when hashes match.

8. What is the average case time complexity of Rabin-Karp?

A) O(n + m)

B) O(nm)

C) O(n log m)

D) O(n^2)

Answer: A) O(n + m)

With a good hash function, Rabin-Karp averages O(n + m) time, though worst case is O(nm).

Z Algorithm

9. What does the Z array store in the Z algorithm?

A) Length of longest substring starting at index i that matches the prefix

B) The number of occurrences of each character

C) The positions of all pattern matches

D) The hash values of all substrings

Answer: A) Length of longest substring starting at index i that matches the prefix

The Z array stores the length of the longest substring starting from position i which is also a prefix of the string.

10. What is the time complexity of the Z algorithm?

A) O(n)

B) O(n log n)

C) O(n + m)

D) O(n^2)

Answer: A) O(n)

The Z algorithm runs in linear time O(n) where n is the length of the string.

Trie Algorithm

11. What is the main advantage of using a trie for string matching?

A) Constant time search

B) Efficient prefix searches

C) Minimal space usage

D) Works well with binary data

Answer: B) Efficient prefix searches

Tries excel at prefix searches and can find all words with a given prefix efficiently.

12. What is the time complexity for searching a string of length m in a trie?

A) O(1)

B) O(m)

C) O(log m)

D) O(n)

Answer: B) O(m)

Trie search time is proportional to the length of the string being searched.