BF

BF (Brute Force)

Finding one string inside another is called pattern matching. The string being searched is the text, and the substring being sought is the pattern.

The simplest algorithm is brute-force matching: compare characters at corresponding positions one by one.

Let S be the text and P the pattern:

1. If the current characters match, S[i] == P[j], increment both i and j and compare the next pair.

2. If they mismatch, S[i] != P[j], set i = i − j + 1 and j = 0. After each failed attempt, i backtracks and j resets to zero.

For example, S = "BBC ABCDAB ABCDABCDABDE" and P = "ABCDABD".

S[0] is B and P[0] is A, a mismatch under case 2.

Next compare S[1] with P[0], equivalent to shifting the pattern one position to the right. They still mismatch under case 2.

Then compare S[2] with P[0] and shift again. Eventually S[4] matches P[0] under case 1.

Now i = 5 and j = 1. S[5] matches P[1], giving i = 6 and j = 2.

Eventually S[10] is a space and P[6] is D: a mismatch under case 2.

Then i = 5 and j = 0, so compare S[5] with P[0].

Continue in this way until the pattern is found or the text is exhausted.

BF takes $O(mn)$ time in the worst case.

BF

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

int brute_force(const char *s, const char *p) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    int i = 0;
    int j = 0;

    while (i < s_len && j < p_len) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == p_len) {
        return i - j;
    } else {
        return -1;
    }
}

int main(void) {
    const char *s = "BBC ABCDAB ABCDABCDABDE";
    const char *p = "ABCDABD";
    printf("%d\n", brute_force(s, p));
    return 0;
}

Return the start index of the first full match, or −1 if no match exists. An empty pattern returns 0. C/C++ operate on bytes, Java on UTF-16 code units, and Python on characters; these examples use ASCII.