# Is that would be better approach to naive algorithm?

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)
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.

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
}

• What if I consider average case what do you think ? It would be better than naive or similar I think you should test my implementation based on your test cases to figure out the drastic changes . Feb 20, 2017 at 17:32
• @sagar I think you should figure out this is simpler and more efficient code to do exactly what you are trying to do and it is the common definition of naive. Feb 20, 2017 at 17:35
• I will not argue with that statement "in worst case its complexity would be O(mn) because you are exactly right about that" but what I found was that If I don't take worst case then Its totally different as my loop was running only twice of the size of Text string and there was no effect of pattern string while naive approach have. And this is what confusing me to take decision that naive is similar. Feb 20, 2017 at 19:08

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.

• But I found that there was a drastic change from my approach as I tested for a string using std. Naive and my approach I found Std. Naive pattern run the loop for 20 times but my approach run it in for only 13 times. Feb 20, 2017 at 3:35
• Sorry but I am weak in understanding theorem of mathematics so can't understand you exactly . It would be good if you give an example. Feb 20, 2017 at 3:51
• and my loop back is not "i-j" it is actually "i-j+1" Feb 20, 2017 at 4:15

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.

• As you said I figure out it is much better approach in average case as I take some test cases and found that my approach was able to found the pattern within twice the size of text string Feb 20, 2017 at 17:29