The naive string matching algorithm is a straightforward approach to find occurrences of a pattern string within a larger text. It checks for a match at every position in the text, making it inefficient for large datasets.

Algorithm Steps:

1. Start from the beginning of the text and compare the pattern with the substring of the text.

2. Move one character forward and repeat the comparison until the end of the text.

3. Record the positions where the pattern matches the substring.


public class NaiveStringMatching {
    public static void search(String txt, String pat) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++)
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;
            if (j == M)
                System.out.println("Pattern found at index " + i);
        }
    }

    public static void main(String[] args) {
        String txt = "ABABDABACDABABCABAB";
        String pat = "ABABCABAB";
        search(txt, pat);
    }
}

Console Output:

Pattern found at index 10

Brute Force String Matching

Concept Overview:

The brute force string matching algorithm is similar to the naive approach, where each character of the pattern is compared with the text until a match is found or the text is exhausted.

Algorithm Steps:

1. Iterate over the text and attempt to match the pattern starting at each position.

2. If a mismatch is found, move to the next position in the text.

3. Continue until a match is found or the end of the text is reached.


public class BruteForceStringMatching {
    public static void search(String txt, String pat) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++)
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;
            if (j == M)
                System.out.println("Pattern found at index " + i);
        }
    }

    public static void main(String[] args) {
        String txt = "THIS IS A TEST TEXT";
        String pat = "TEST";
        search(txt, pat);
    }
}

Console Output:

Pattern found at index 10

Pattern Searching with Wildcards

Concept Overview:

In some cases, the pattern may include wildcards, which can match any character. The naive algorithm can be adapted to handle these wildcards efficiently.

Algorithm Steps:

1. Iterate over the text and attempt to match the pattern, accounting for wildcards.

2. Compare characters unless a wildcard is encountered, which matches any character.

3. Record matches and continue searching through the text.


public class WildcardStringMatching {
    public static boolean match(String txt, String pat) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++)
                if (pat.charAt(j) != '?' && txt.charAt(i + j) != pat.charAt(j))
                    break;
            if (j == M)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String txt = "GEEKSFORGEEKS";
        String pat = "G??KS";
        if (match(txt, pat))
            System.out.println("Pattern matches");
        else
            System.out.println("Pattern does not match");
    }
}

Console Output:

Pattern matches

Case-Insensitive String Matching

Concept Overview:

Case-insensitive string matching involves comparing strings without considering the case of the characters, making it useful for user input validation or search functionalities.

Algorithm Steps:

1. Convert both the text and pattern to the same case (either lower or upper).

2. Apply the naive string matching algorithm on the converted strings.

3. Record the positions of matches as usual.


public class CaseInsensitiveMatching {
    public static void search(String txt, String pat) {
        txt = txt.toLowerCase();
        pat = pat.toLowerCase();
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++)
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;
            if (j == M)
                System.out.println("Pattern found at index " + i);
        }
    }

    public static void main(String[] args) {
        String txt = "Hello World";
        String pat = "WORLD";
        search(txt, pat);
    }
}

Console Output:

Pattern found at index 6

Reverse String Matching

Concept Overview:

Reverse string matching involves searching for a pattern in the reverse order. This can be useful in scenarios where data is processed backwards or in reverse chronological order.

Algorithm Steps:

1. Reverse both the text and the pattern.

2. Apply the naive string matching algorithm on the reversed strings.

3. Record the positions of matches, adjusting for the original order.


public class ReverseStringMatching {
    public static String reverse(String str) {
        return new StringBuilder(str).reverse().toString();
    }

    public static void search(String txt, String pat) {
        txt = reverse(txt);
        pat = reverse(pat);
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++)
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;
            if (j == M)
                System.out.println("Pattern found at reversed index " + (N - i - M));
        }
    }

    public static void main(String[] args) {
        String txt = "ABCDEDCBA";
        String pat = "EDC";
        search(txt, pat);
    }
}

Console Output:

Pattern found at reversed index 2