Pattern Matching in Java: Naive Search vs KMP Explained

Ever wondered how:

• browsers search text
• editors find words
• search engines process patterns

It all starts with:

• Pattern Matching.

The goal is simple:
Find a smaller string (pattern)
inside a larger string (text).

1. Naive Pattern Matching

The simplest approach:

• Check every possible starting position.

public static int naiveSearch(String text, String pattern) {

int n = text.length();
int m = pattern.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;

}

How It Works

Example:

Text:

ABABDABACDABABCABAB

Pattern:

ABABC

• Start checking from every position.

If mismatch occurs:

• shift pattern by one step.

Problem with Naive Approach

Worst-case complexity:

O(n×m)

Because:

• characters get rechecked multiple times.

2. KMP Algorithm (Basic Idea)

KMP improves performance using:

• LPS array (Longest Prefix Suffix)

Instead of restarting from zero:

• it uses previous match information.

KMP Complexity

O(n+m)

This is much faster for large strings.

KMP is powerful because it:

• remembers previous matches
• avoids unnecessary comparisons

That’s the optimization.

• Pattern matching = substring search
• Naive approach is simple but slower
• KMP uses preprocessing for speed

Vist Full Tutorials Here: https://www.quipoin.com/tutorial/data-structure-with-java/pattern-matching-basics