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?

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?

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?

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?

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:

Space Complexity: O(1).

16. What are the advantages and disadvantages of Rabin-Karp?

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?

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?

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?

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?

25. What is the time and space complexity of Suffix Arrays?

Time Complexity:

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?

28. What are the applications of Suffix Trees?

29. What are the time and space complexities of Suffix Trees?

Time Complexity:

Space Complexity: O(n) (compressed trie structure).

30. What are the advantages and disadvantages of Suffix Arrays vs. Suffix Trees?

Suffix Arrays:

Suffix Trees:

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.