Naive Pattern Matching (String Pattern Searching) in Java

Naive Pattern Matching (String Pattern Searching)

Find all occurrences of a pattern string within a given text using the simplest character-by-character comparison approach.

---

Problem Statement

Given a text string txt and a pattern string pat, print all starting indices where the pattern occurs in the text. The pattern must match completely and contiguously.

Examples:

Input:
txt = "ABABABCD"
pat = "ABAB"

Output:
0 2

Input:
txt = "ABCABCD"
pat = "ABCD"

Output:
3

Input:
txt = "AAAAA"
pat = "AAA"

Output:
0 1 2

---

Approaches Used

• Naive Pattern Matching (Brute Force)

---

Java Code Implementation

public class NaivePatternMatching {

    public static void main(String[] args) {

        // Multiple test cases
        searchPattern("ABABABCD", "ABAB");   // Expected: 0 2
        searchPattern("ABCABCD", "ABCD");    // Expected: 3
        searchPattern("AAAAA", "AAA");       // Expected: 0 1 2
    }

    private static void searchPattern(String text, String pattern) {

        int n = text.length();
        int m = pattern.length();

        System.out.println("Text: " + text + ", Pattern: " + pattern);

        for (int i = 0; i <= n - m; i++) {
            int j;

            // Compare pattern with substring starting at i
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }

            // If full pattern matched
            if (j == m) {
                System.out.print(i + " ");
            }
        }
        System.out.println("\n");
    }
}

---

Explanation

Approach 1

• Slide the pattern one character at a time over the text.
• At each position, compare the pattern with the corresponding substring.
• If all characters match, print the current index.
• Continue until the remaining text length is less than the pattern length.

Technique Used: Brute Force / Naive String Matching

---

Sample Output

Text: ABABABCD, Pattern: ABAB
0 2

Text: ABCABCD, Pattern: ABCD
3

Text: AAAAA, Pattern: AAA
0 1 2

---

Time & Space Complexity

Approach	Time	Space
Naive Pattern Matching	O((n - m + 1) × m)	O(1)

---

Interview Tip

Always start with the naive approach in interviews, then optimize to KMP or Rabin–Karp when asked about performance improvements.

---

Practice More

• Implement KMP Pattern Matching Algorithm
• Pattern matching using Rabin–Karp (Rolling Hash)

---

Category: Strings
Difficulty: Easy
Techniques: Brute Force, String Matching