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