13. Brute Force Pattern Matching Algorithm

Pattern matching is quite important in today's age, mainly with natural language processing, information retrieval, spam dectection, etc. This develops a need for efficent pattern matching algorithms.

Some defintions with $S[i \cdots j]$ is a contiguous substring of $S$ starting at position $i$ and ending at position $j$ or $N-1$ of $S$:

• $S[0 \cdots j]$ is a prefix of $S$ starting at position $0$ and ending at position $j$
• $S[i \cdots N-1]$ is a suffix of $S$ starting at position $i$ and running till $N-1$

Let's say we want to find a pattern within a string. So, let's simply compare left to right, character by character. If there is a mismatch, then go one over and restart the process.

public static int bruteForceFind(String text, String pattern) {
    int m = pattern.length();
    int n = text.length();

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text.charAt(i+j) != pattern.charAt(j)) {
                break;
            }
        }
        if (j == m) return i;
    }
    return -1;
}

This time complexity will be $O(NM)$ which is not optimal.

Next Page →