Naive Distinct Pattern Matching in Strings in Java

Naive Distinct Pattern Matching in Strings

An optimized version of naive pattern matching that skips unnecessary comparisons when the pattern contains all distinct characters.

---

Problem Statement

Given a text string txt and a pattern string pat (with all distinct characters), find and print all starting indices where the pattern occurs in the text.

Examples:

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

Output:
3

Input:
txt = "ABCEABCFABCD"
pat = "ABCD"

Output:
8

---

Approaches Used

• Naive Pattern Matching
• Naive Distinct Pattern Matching (Optimized)

---

Java Code Implementation

public class NaiveDistinctPatternMatching {

    public static void main(String[] args) {

        // Multiple test cases
        searchDistinctPattern("ABCABCD", "ABCD");        // Expected: 3
        searchDistinctPattern("ABCEABCFABCD", "ABCD");  // Expected: 8
        searchDistinctPattern("XYZABCDXYZ", "ABCD");    // Expected: 3
    }

    private static void searchDistinctPattern(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; ) {
            int j;

            // Match characters
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }

            // Full pattern matched
            if (j == m) {
                System.out.print(i + " ");
            }

            // Skip logic (key optimization)
            if (j == 0) {
                i++;
            } else {
                i = i + j;
            }
        }
        System.out.println("\n");
    }
}

---

Explanation

Approach 1: Naive Pattern Matching

• Slide the pattern one character at a time.
• Compare every character even if a mismatch occurs early.
• Always increment index by 1.

Technique Used: Brute Force String Matching

---

Approach 2: Naive Distinct Pattern Matching

• Works only when pattern characters are all distinct.
• If a mismatch happens at index j, skip ahead by j characters.
• Avoids rechecking characters that are guaranteed not to match.
• Significantly reduces unnecessary comparisons.

Technique Used: Optimized Brute Force (Distinct Characters Optimization)

---

Sample Output

Text: ABCABCD, Pattern: ABCD
3

Text: ABCEABCFABCD, Pattern: ABCD
8

Text: XYZABCDXYZ, Pattern: ABCD
3

---

Time & Space Complexity

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

---

Interview Tip

Mention that this optimization works only when all characters in the pattern are distinct. Otherwise, use KMP for guaranteed linear performance.

---

Practice More

• Compare Naive Distinct vs KMP with examples
• Implement pattern matching using Z-algorithm

---

Category: Strings
Difficulty: Easy
Techniques: Brute Force, Pattern Matching, Optimization

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