Naive Algorithm to Search Pattern in Java

In this article, we will deal with pattern searching in a string using the Naive Algorithm in Java programming. The main objective is to find how many times the substring occurs in a given string and at what positions the substring occurs in the text. There are different pattern searching algorithms, but we will use the naive method for the implementation.

It is the brute-force method of searching. It is helpful for small texts.

The method checks for all the characters in the main string with the substring. If the first letter of the string matches with the main string then we start an inner loop and check the next elements. If all the elements in the substring match with the main string then we will return the starting index of the main string and again we will check for the next occurrences. This algorithm is helpful for small strings only because for long strings it will consume too much time. Nevertheless, it is a good searching method for beginners to understand pattern searching.

Examples:

Input:  str[] = "Welcome to CodeSpeedy"
        pat[] = "CodeSpeedy"
Output: Pattern occurs at index 11

Input:  txt[] = "AABAACAADAABAABA"
        pat[] = "AABA"
Output: Pattern occurs at index 0
        Pattern occurs at index 9
        Pattern occurs at index 12

Naive Pattern Search Algorithm:

SEARCH(str, pattern)

 1. n = length [str]
 2. m = length [pattern]
 3. for s = 0 to n -m do
 4. if P [1.....m] = T [s + 1....s + m]
 5. then print s

Given below is the code implementation in Java for pattern search with Naive Algorithm:

public class Naive { 
  
    public static void search(String str, String pattern) 
    { 
        int n = str.length(); 
        int m = pattern.length(); 
        
        for (int s = 0; s <= n - m; s++) { 
            int j; 
            for (j = 0; j < m; j++) 
                if (str.charAt(s + j) != pattern.charAt(j)) 
                    break; 
            if (j == m) 
                System.out.println("Pattern occurs at index " + s); 
        } 
    } 
  
    public static void main(String[] args) 
    { 
        String txt = "AABAACAADAABAAABAA"; 
        String pat = "AABA"; 
        search(txt, pat); 
    } 
}

Output

Pattern occurs at index 0
Pattern occurs at index 9
Pattern occurs at index 13

In the above code ‘search’ takes two arguments ‘str'(main string) and ‘pattern'(SubString). A loop is taken from 0 to (n-m). Each character is extracted from the main String and matched with the substring through the for loop from 0 to substring length. If they don’t match the inside loop breaks and the outside loop increase by 1 and repeat the previous steps until the outside loop completes.

Best Case- The best case is when the first character of the substring doesn’t match with the main string throughout the whole searching process.

Worst Case- The worst case is when only the last character is different or all characters are same. example- String-“BBBBBBBBB” and SubString-“BBB” or “BBBC”.

The time complexity of Naive pattern searching algorithm is O(m*n) where m is the length of the pattern and n is the length of the main String.

Also read our article: How to implement KMP String Matching algorithm in Python.