String Searching (Naive)

You type “rain” in a search box. The app has to tell you if that word sits somewhere inside a big block of text. How does it actually find it? The simplest way is naive search. Naive search just tries to match your pattern starting at every single spot in the text. It keeps trying until it finds one that fits.

In this tutorial we will build a small function. You give it a text and a pattern. It returns the first index where the pattern shows up. If the pattern is not there, it returns -1.

📚 What Is Naive String Searching?

Say you are reading a book and looking for the word “rain”. You put your finger on the first letter. You check if the next few letters spell “rain”. No? Then you move your finger one letter to the right and check again. You keep sliding until you find it or reach the end.

That sliding-and-checking is exactly what naive string searching does. It slides the pattern across the text one position at a time. At each stop it compares letter by letter.

Let us fix some words first so nothing feels confusing later.

• Text is the big string you search inside. Think of it as the full page.
• Pattern is the small string you are looking for. Think of it as the word you want to find.
• Match means every character of the pattern lines up with the text at that position.

So say the text is ABCABD and the pattern is ABD. The answer is index 3. That is where ABD starts inside the text.

🧠 How The Sliding Works

Picture the pattern as a small window. You place that window at the start of the text. Then you compare character by character.

Here is the key thing. At every start position we do a full check of the pattern. If even one character is wrong, we stop checking that position. Then we slide one step to the right and start a fresh check.

Let us trace text = "AABAACAADAABAABA" and pattern = "AABA".

• Start at index 0. Compare AABA with AABA. All four match. We found it. Return 0.

That one was easy. Now imagine the pattern was AADA instead. We would fail at index 0 on the third letter. So we slide right and keep going. We reach index 6, where AADA lines up.

🪜 Steps To Search Naively

Before we write code, let us lay out the plan in plain steps. Follow these and the code will read like a story.

1. Let n be the length of the text and m be the length of the pattern.
2. Loop a start index i from 0 up to n - m. We stop at n - m because past that point the pattern cannot fit.
3. For each i, loop an inner index j from 0 to m - 1.
4. Compare text[i + j] with pattern[j]. If they differ, break out of the inner loop. This start position failed.
5. If the inner loop finished without breaking, every character matched. Return i.
6. If the outer loop ends and nothing matched, return -1.

💻 The Code In Five Languages

Now we turn those steps into a real function. The function is called naiveSearch. It takes the text and the pattern. Then it returns the first matching index, or -1.

#include <stdio.h>
#include <string.h>

// Returns the first index where pattern is found in text, or -1.
int naiveSearch(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    // Try every start position that still has room for the pattern.
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Compare the pattern against the text at this start.
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i; // All characters matched.
        }
    }
    return -1; // Pattern not found anywhere.
}

int main() {
    const char *text = "AABAACAADAABAABA";
    const char *pattern = "AABA";

    int index = naiveSearch(text, pattern);
    printf("Pattern first found at index: %d\n", index);
    return 0;
}

Pattern first found at index: 0

#include <iostream>
#include <string>
using namespace std;

// Returns the first index where pattern is found in text, or -1.
int naiveSearch(const string &text, const string &pattern) {
    int n = text.size();
    int m = pattern.size();

    // Try every start position that still has room for the pattern.
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Compare the pattern against the text at this start.
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return i; // All characters matched.
        }
    }
    return -1; // Pattern not found anywhere.
}

int main() {
    string text = "AABAACAADAABAABA";
    string pattern = "AABA";

    int index = naiveSearch(text, pattern);
    cout << "Pattern first found at index: " << index << endl;
    return 0;
}

Pattern first found at index: 0

public class NaiveSearch {

    // Returns the first index where pattern is found in text, or -1.
    static int naiveSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        // Try every start position that still has room for the pattern.
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            // Compare the pattern against the text at this start.
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i; // All characters matched.
            }
        }
        return -1; // Pattern not found anywhere.
    }

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

        int index = naiveSearch(text, pattern);
        System.out.println("Pattern first found at index: " + index);
    }
}

Pattern first found at index: 0

# Returns the first index where pattern is found in text, or -1.
def naive_search(text, pattern):
    n = len(text)
    m = len(pattern)

    # Try every start position that still has room for the pattern.
    for i in range(n - m + 1):
        j = 0
        # Compare the pattern against the text at this start.
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i  # All characters matched.
    return -1  # Pattern not found anywhere.


text = "AABAACAADAABAABA"
pattern = "AABA"

index = naive_search(text, pattern)
print("Pattern first found at index:", index)

Pattern first found at index: 0

// Returns the first index where pattern is found in text, or -1.
function naiveSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;

  // Try every start position that still has room for the pattern.
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    // Compare the pattern against the text at this start.
    while (j < m && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === m) {
      return i; // All characters matched.
    }
  }
  return -1; // Pattern not found anywhere.
}

const text = "AABAACAADAABAABA";
const pattern = "AABA";

const index = naiveSearch(text, pattern);
console.log("Pattern first found at index:", index);

Pattern first found at index: 0

⏳ How Fast Is It?

Let us think about the worst case. Imagine the text is AAAAAAAA and the pattern is AAAB. At almost every start position the first few characters match. Then the last one fails. So the inner loop runs nearly the full pattern length again and again.

Here is the cost in one table.

The reason naive search can be slow is that it forgets what it already learned. When a match fails, it slides just one step and starts over from scratch. A smarter algorithm called KMP remembers the matched part and skips ahead instead of restarting. We cover that next.

⚠️ Common Mistakes

A few small slips trip up most people the first time. Watch out for these.

• Letting the outer loop run all the way to n instead of n - m. Then text[i + j] reads past the end of the string. You get a crash or wrong data.
• Forgetting the j == m check after the inner loop. Without it you never confirm a full match.
• Returning the wrong index. You want the start index i, not the inner counter j.
• Mixing up text and pattern. The pattern is the small one you search for. The text is the big one you search inside.

🧩 What You’ve Learned

✅ Naive string searching slides the pattern across the text and checks character by character at each start position.

✅ You stop the outer loop at n - m so the pattern never runs off the end of the text.

✅ The function returns the first matching index, or -1 when the pattern is not present.

✅ The worst case time is O(n*m). That is fine for small inputs but slow for long ones.

✅ KMP improves on this by remembering matched characters instead of restarting after every failure.

🚀 What’s Next?

• String Pattern Matching (KMP)
• String Operations