Brute Force String Matching

Brute force string matching is a straightforward algorithm used to find occurrences of a pattern within a text. It works by systematically checking if the pattern matches a substring at each position in the text. If a match is found, the algorithm proceeds to verify if the entire pattern matches the substring. This process continues until either a match is found or the end of the text is reached without finding any matches. While simple, brute force string matching can be inefficient for large texts or patterns due to its time complexity, which is typically O(n⋅m)O(n⋅m), where nn is the length of the text and mm is the length of the pattern. Despite its inefficiency, it serves as a fundamental building block in understanding more sophisticated string matching algorithms.

def brute_force_string_match(text, pattern):
    n = len(text)
    m = len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m:
            if text[i + j] != pattern[j]:
                break
            j += 1
        if j == m:
            return i
    return -1


          

#include <stdio.h>
#include <string.h>

int brute_force_string_match(char* text, char* pattern) {
    int n = strlen(text);
    int 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) {
            return i;
        }
    }
    return -1;
}

int main() {
    char text[] = "ABABCABABABAABCABAB";
    char pattern[] = "ABAB";
    int position = brute_force_string_match(text, pattern);
    if (position != -1) {
        printf("Pattern found at position: %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }
    return 0;
}