Is that would be better approach to naive algorithm?

Question

I was studying about naive pattern search algorithm and found that it requires two loops to match the pattern present in a string or not. That time an Idea stuck in my mind and I think it would be a better approach because I used only one loop to find out the pattern in string. Here is

Pseudocode

MY-PAT-ALGO(T[n],P[m])
[Here, T[n] is text string of length n and P[m] is pattern string of length m]
1. j <-- 0 , flag <-- 0
2. for i<-- 0 to n
   do 
      if(T[i] = P[j])
         j<-- j+1
      else
         i<-- i-j
         j<-- 0
      end else-if

      if(j = m)
        flag <-- 1
        Print: "Pattern matched"
        break
      end if
  end for loop
3. if(flag = 0)
      Print: "Pattern not found"
4. Exit.

I want to know why it could be worst in comparison of naive approach. According to my test cases I found loop worst case is better than naive approach loop.

Answer 1

Let N be the length of the string you are searching
Let M be the length of the sub-string you are searching for

I bet you are using a definition of naive as searching the full M every time. The common definition is stop at the first mismatch. It is worse case $\mathcal{O}(mn)$.

A simpler and more efficient implementation compare to your code

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)  
         // done
}

Answer 2

It does have only one loop, but you are modifying the controlling counter ($i$). And because you reduce it by an amount proportional to the size of your pattern, I presume it is $\mathcal{O}(mn)$.

A test case could be $T_n=a_1a_2a_3...a_{n-1}x_n$ and $P_m=a_1a_2a_3...a_{m-1}x_m$ (Both are 'a's followed by an 'x'). Evidently the match will only be at the end, however it should find partial matchings at every previous positions. If you try for different $n$ and $m$ and the amount of comparisons are proportional to $mn$, then it is fundamentally the same as the naive approach.

If you want a better performance in perfect pattern matching, you could use the z-algorithm or the prefix-function (KMP is also for pattern matching, but it is space improved use of prefix-function). They work in $\mathcal{O}(m+n)$-time.

By the way, to compare algorithms (one common way but not the only one) is the Big-O Notation.

Answer 3

Your approach is the naive approach. Given a pattern of length $m$, you try to match characters $i$, $i+1$, ... $i+m-1$ of the string against characters $1$, $2$, ..., $m$ of the pattern. If they all match, you report success; otherwise, you start again at the start of the pattern and character $i+1$ of the string.