Pattern Matching & Trie in C: Naive, KMP, Rabin-Karp, Suffix Array/Tree with Code Examples
1. What is pattern matching in strings?
Pattern matching involves finding all occurrences (or the first occurrence) of a pattern string within a text string. It’s used in search engines, text editors, and bioinformatics.
2. What are the common pattern matching algorithms?
Naive, Knuth-Morris-Pratt (KMP), Rabin-Karp.
3. What is the Naive Pattern Matching algorithm?
The Naive algorithm slides the pattern over the text, checking for a match at each position by comparing characters one by one.
4. Can you give an example of Naive Pattern Matching in C?
#include <stdio.h>
#include <string.h>
void naivePatternMatch(char* text, char* pattern) {
int n = strlen(text), m = strlen(pattern);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) break;
}
if (j == m) printf("Pattern found at index %d\n", i);
}
}
int main() {
char text[] = "AABAACAADAABAAABAA";
char pattern[] = "AABA";
naivePatternMatch(text, pattern); // Output: Pattern found at index 0, 9, 13
return 0;
}
5. What is the time complexity of Naive Pattern Matching?
Time Complexity: O(n * m) (n = text length, m = pattern length).
Space Complexity: O(1).
6. What are the advantages and disadvantages of Naive Pattern Matching?
- Advantages: Simple, no preprocessing, works for all inputs.
- Disadvantages: Inefficient for large texts or patterns.
7. What is the KMP Algorithm?
KMP is an efficient pattern matching algorithm that avoids redundant comparisons by using a partial match table (LPS array) to skip unnecessary checks.
8. How does KMP work?
- Compute the Longest Proper Prefix which is also Suffix (LPS) array for the pattern.
- Use LPS to skip redundant comparisons when a mismatch occurs during matching.
9. Can you give an example of KMP in C?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void computeLPS(char* pattern, int m, int* lps) {
int len = 0, i = 1;
lps[0] = 0;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) len = lps[len - 1];
else lps[i] = 0, i++;
}
}
}
void KMP(char* text, char* pattern) {
int n = strlen(text), m = strlen(pattern);
int* lps = (int*)malloc(m * sizeof(int));
computeLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (pattern[j] == text[i]) i++, j++;
if (j == m) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
free(lps);
}
int main() {
char text[] = "AABAACAADAABAAABAA";
char pattern[] = "AABA";
KMP(text, pattern); // Output: Pattern found at index 0, 9, 13
return 0;
}
10. What is the time complexity of KMP?
Time Complexity: O(n + m) (n = text length, m = pattern length).
Space Complexity: O(m) (LPS array).
11. What are the advantages and disadvantages of KMP?
- Advantages: Linear time complexity, efficient for large texts.
- Disadvantages: Requires preprocessing, more complex than Naive.
12. What is the Rabin-Karp Algorithm?
Rabin-Karp uses hashing to find pattern matches by comparing hash values of the pattern and text substrings, reducing character comparisons.
13. How does Rabin-Karp work?
- Compute the hash of the pattern and the first text window.
- Slide the window, updating the hash using a rolling hash function.
- If hashes match, verify characters to confirm a match.
14. Can you give an example of Rabin-Karp in C?
#include <stdio.h>
#include <string.h>
#define d 256 // Number of characters in input alphabet
#define q 101 // A prime number for modulo
void rabinKarp(char* text, char* pattern) {
int n = strlen(text), m = strlen(pattern);
int p = 0, t = 0, h = 1;
// Calculate h = pow(d, m-1) % q
for (int i = 0; i < m - 1; i++) h = (h * d) % q;
// Calculate hash for pattern and first window
for (int i = 0; i < m; i++) {
p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}
// Slide window
for (int i = 0; i <= n - m; i++) {
if (p == t) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) break;
}
if (j == m) printf("Pattern found at index %d\n", i);
}
if (i < n - m) {
t = (d * (t - text[i] * h) + text[i + m]) % q;
if (t < 0) t += q;
}
}
}
int main() {
char text[] = "AABAACAADAABAAABAA";
char pattern[] = "AABA";
rabinKarp(text, pattern); // Output: Pattern found at index 0, 9, 13
return 0;
}
15. What is the time complexity of Rabin-Karp?
Time Complexity:
- Average:
O(n + m) - Worst:
O(n * m)(due to hash collisions).
Space Complexity: O(1).
16. What are the advantages and disadvantages of Rabin-Karp?
- Advantages: Efficient average case, can handle multiple patterns.
- Disadvantages: Hash collisions may degrade performance, requires good hash function.
17. What are Trie-based problems?
Trie-based problems involve using a Trie (prefix tree) to solve string-related tasks, leveraging its ability to efficiently store and search strings based on prefixes.
18. What are common Trie-based problems?
- Word search (e.g., dictionary lookup).
- Autocomplete suggestions.
- Longest common prefix.
- Pattern matching with wildcards.
19. Can you give an example of a Trie-based problem (Longest Common Prefix) in C?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
int count; // Number of words passing through this node
bool isEndOfWord;
};
struct TrieNode* createNode() {
struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
node->count = 0;
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++) node->children[i] = NULL;
return node;
}
void insert(struct TrieNode* root, char* word) {
struct TrieNode* curr = root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (!curr->children[index]) curr->children[index] = createNode();
curr = curr->children[index];
curr->count++;
}
curr->isEndOfWord = true;
}
char* longestCommonPrefix(char* words[], int n) {
struct TrieNode* root = createNode();
for (int i = 0; i < n; i++) insert(root, words[i]);
char* result = (char*)malloc(100 * sizeof(char));
int len = 0;
struct TrieNode* curr = root;
while (curr) {
int singleChild = -1, count = 0;
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (curr->children[i]) {
singleChild = i;
count++;
}
}
if (count != 1 || curr->count != n) break;
result[len++] = 'a' + singleChild;
curr = curr->children[singleChild];
}
result[len] = '\0';
// Note: Full cleanup requires recursive free of Trie nodes
return result;
}
int main() {
char* words[] = {"flower", "flow", "flight"};
int n = 3;
char* lcp = longestCommonPrefix(words, n);
printf("%s\n", lcp); // Output: fl
free(lcp);
return 0;
}
20. What are the time and space complexities for Trie-based problems?
For Longest Common Prefix:
Time Complexity: O(S) (S = total length of all strings for insertion, min length for LCP).
Space Complexity: O(S * ALPHABET_SIZE) (Trie storage).
21. What are the advantages of Tries for string problems?
- Advantages: Fast prefix-based operations, efficient for dictionary-like tasks.
- Disadvantages: High memory usage, complex for non-alphabetic data.
22. What is a Suffix Array?
A Suffix Array is an array of integers representing the starting positions of all suffixes of a string, sorted in lexicographical order. It’s used for efficient string matching and substring queries.
23. How is a Suffix Array constructed?
- Generate all suffixes of the string.
- Sort them lexicographically.
- Store their starting indices in an array.
Efficient construction uses algorithms like DC3/Skew (O(n)) or sorting-based methods (O(n log n)).
24. What are the applications of Suffix Arrays?
- Pattern matching (faster than Naive, comparable to KMP).
- Longest common substring.
- Substring search and counting.
25. What is the time and space complexity of Suffix Arrays?
Time Complexity:
- Construction:
O(n log n)(sorting-based) orO(n)(advanced algorithms). - Query:
O(m + log n)for pattern matching (m = pattern length, using binary search).
Space Complexity: O(n) (array storage).
26. What is a Suffix Tree?
A Suffix Tree is a compressed trie containing all suffixes of a string, where each path from the root to a leaf represents a suffix. Edges store substrings, making it space-efficient for some tasks.
27. How is a Suffix Tree constructed?
- Naive: Insert each suffix into a trie (
O(n²)). - Efficient: Use Ukkonen’s algorithm (
O(n)) for linear-time construction. - Each leaf represents a suffix, and internal nodes represent common prefixes.
28. What are the applications of Suffix Trees?
- Exact string matching (
O(m)). - Longest repeated substring.
- Longest common substring of multiple strings.
- Pattern searching with wildcards.
29. What are the time and space complexities of Suffix Trees?
Time Complexity:
- Construction:
O(n)(Ukkonen’s algorithm). - Query:
O(m)for pattern matching.
Space Complexity: O(n) (compressed trie structure).
30. What are the advantages and disadvantages of Suffix Arrays vs. Suffix Trees?
Suffix Arrays:
- Advantages: Simpler, less memory (
O(n)), easier to implement. - Disadvantages: Slower queries (
O(m + log n)vs.O(m)).
Suffix Trees:
- Advantages: Faster queries (
O(m)), supports complex string operations. - Disadvantages: Higher memory usage, complex construction.
31. Why are Suffix Arrays/Trees used in string algorithms?
They enable efficient substring searches, pattern matching, and other string operations by leveraging the sorted order of suffixes or prefix-based structure, outperforming simpler methods for large strings.
Frequently asked questions
What are common string pattern matching algorithms?
Naive (O(n*m)), KMP (O(n+m)), Rabin-Karp (average O(n+m), worst O(n*m)).
How does KMP algorithm work?
pre computes LPS (Longest Proper Prefix which is Suffix) array to skip redundant comparisons. Linear time.
What is Rabin-Karp algorithm?
Uses rolling hash to compare pattern with text substrings. Efficient average case with hashing.
What is a Trie and its applications?
Prefix tree for efficient string storage/retrieval. Used for autocomplete, longest common prefix, dictionary.
What is Suffix Array?
Sorted array of suffix starting indices. Enables O(m + log n) pattern matching via binary search.
What is Suffix Tree?
Compressed trie of all suffixes. O(m) pattern matching, O(n) construction with Ukkonen’s algorithm.
When to use Suffix Array vs Suffix Tree?
Suffix Array: simpler, less memory. Suffix Tree: faster queries, more complex.