Naïve String Matching Algorithm

String matching is a process used to find one string (called the pattern) inside another larger string (called the text).

The Naïve String Matching Algorithm is the simplest and most basic method for solving this problem. It checks for the pattern at every possible position in the text, one by one.

Although it is not the fastest algorithm, it is easy to understand and works well for small texts.

Quescol 1-Minute Read

The Naïve String Matching Algorithm is the most basic method to find where a small string (called the pattern) appears inside a bigger string (called the text). It works by checking for the pattern at every possible position in the text, moving one character at a time.

It starts from the beginning of the text and compares each character of the pattern with the corresponding character in the text. If all characters match, it returns the position. If a mismatch occurs, it shifts the pattern one position to the right and continues checking. This process continues until the entire text has been scanned.

Here are the main points to remember about Naïve String Matching Algorithm:

• It checks the pattern at each position of the text one by one.
• Uses two loops – one for sliding the pattern and one for comparing characters.
• If all characters match, it prints the index where the pattern is found.
• If a mismatch occurs, it moves the pattern one step forward and continues.
• It’s easy to understand and implement, making it perfect for beginners.
• However, it can be slow for large texts because it compares characters many times.

In short, the Naïve String Matching algorithm is simple, step-by-step, and memory-friendly but not efficient for large-scale problems since it checks every possible position without skipping any.

Let’s Understand in Depth

What is Naïve String Matching Algorithm?

The Naïve String Matching Algorithm compares the pattern with every possible substring of the text. It shifts the pattern by one character at a time and checks whether all characters of the pattern match the corresponding characters of the text.

If a match is found → the algorithm returns the position.
If no match is found → it shifts the pattern and repeats the process until you reach the end of the text.

How It Works?

1. Start from the beginning of the text.
2. Compare the pattern with the current substring of the text — character by character.
3. If all characters match, you have found a match at that position.
4. If there is a mismatch, shift the pattern by one character to the right and repeat the comparison.
5. Continue until you reach the end of the text.

Working Procedure (Step-by-Step)

Imagine you have a text T of length n and a pattern P of length m. You want to see if the pattern occurs anywhere in the text. The naïve string matching method works like this:

1. Start from the beginning of the text:
   • Set i = 0, which means you start checking from the first character of the text.
2. Compare the pattern with the text:
   • Look at the substring of the text that starts at position i and has the same length as the pattern (m characters).
   • Compare each character of the pattern with the corresponding character in this substring one by one.
3. Check if all characters match:
   • If every character in the pattern is the same as the substring, you have found a match.
   • Record this position i because the pattern occurs there.
4. If the pattern does not match:
   • Move the pattern one position to the right in the text.
   • This means increase i by 1.
5. Repeat the process:
   • Keep repeating steps 2–4 until you have checked all possible starting positions in the text.
   • The last starting position to check is i = n - m, because after that the remaining text is shorter than the pattern.
6. Result:
   • At the end, you will have a list of all positions in the text where the pattern occurs.

Example

Text (T): AABAACAADAABAABA
Pattern (P): AABA

Pattern found at positions: 0, 9, and 12

We are trying to find the pattern “AABA” in the text “AABAACAADAABAABAP” using the naïve string matching method. We start from the beginning of the text and compare the pattern with each substring of the same length.

• At shift 0, the first four letters of the text “AABA” exactly match the pattern, so we record a match at index 0.
• We then move one position to the right and compare again. Most of these shifts (1 to 8) do not match the pattern.
• At shift 9, the substring “AABA” again matches the pattern, so we record a match at index 9.
• Finally, at shift 12, the substring “AABA” matches once more, giving us a match at index 12.

So, the pattern “AABA” appears in the text at positions 0, 9, and 12. It’s basically checking every possible starting position in the text to see if the pattern fits.

Algorithm: (Naive-String-Match(T, P))

1. Start
2. Input: Text T of length n, Pattern P of length m
3. Output: All positions where P occurs in T
4. for i = 0 to n - m do
5.     Set j = 0
6.     while j < m and T[i + j] == P[j] do
7.         j = j + 1
8.     if j == m then
9.         Print “Pattern found at index i”
10. end for
11. End

Java Program to implement Naïve String Matching

public class NaiveStringMatching {
    // Function to perform naive pattern searching
    public static void search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        // Slide the pattern one by one
        for (int i = 0; i <= n - m; i++) {
            int j;

            // Check for match
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // mismatch found
                }
            }

            // If full pattern matched
            if (j == m) {
                System.out.println("Pattern found at index " + i);
            }
        }
    }

    public static void main(String[] args) {
        String text = "AABAACAADAABAABA";
        String pattern = "AABA";
        search(text, pattern);
    }
}

Output

Pattern found at index 0
Pattern found at index 9
Pattern found at index 12

Explanation of the above Code

This Java code explains the Naïve String Matching algorithm, which is a simple way to find where a small string (called the pattern) appears inside a larger string (called the text).

The program starts with the function search(String text, String pattern). It first finds the length of the text (n) and the length of the pattern (m). Then, it slides the pattern over the text one position at a time using a for loop (for (int i = 0; i <= n - m; i++)).

For every position i, another loop (for (j = 0; j < m; j++)) checks each character of the pattern with the corresponding character in the text. If a mismatch is found (if (text.charAt(i + j) != pattern.charAt(j))), the loop breaks and moves to the next position.

If all characters match perfectly (if (j == m)), it means the pattern is found starting from that index, and the program prints “Pattern found at index i”.

In the main() method, the text "AABAACAADAABAABA" and the pattern "AABA" are given. The function then finds all the positions where "AABA" appears in the text.

Naïve String Matching Algorithm Complexity

Time Complexity

Space Complexity

Conclusion

The Naïve String Matching Algorithm is a simple method to find a small string, called a pattern, inside a larger string, called the text. It works by checking the pattern at every possible position in the text, one by one, and records the positions where all characters match. The algorithm is easy to understand, implement, and uses very little memory, making it ideal for beginners and small texts. However, it can be slow for large texts because it compares characters at every position without skipping, so it is not efficient for large-scale text searching.