Naive Pattern Searching algorithm

Naive pattern searching is the simplest method among other pattern-searching algorithms. It checks for all characters of the main string to the pattern. This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find the substring by checking once for the string. It also does not occupy extra space to perform the operation.

Time Complexity: O(N*M)

Auxiliary Space: O(1)

Example:

#include <bits/stdc++.h>

using namespace std;

void search(char* pat, char* txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

    /* A loop to slide pat[] one by one */

    for (int i = 0; i <= N - M; i++) {

        int j;

        /* For current index i, check for pattern match */

        for (j = 0; j < M; j++)

            if (txt[i + j] != pat[j])

                break;

        if (j

            == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]

            cout << "Pattern found at index " << i << endl;

    }

}

// Driver's Code

int main()

{

    char txt[] = "AABAACAADAABAAABAA";

    char pat[] = "AABA";

    // Function call

    search(pat, txt);

    return 0;

}