String Search Algorithm Implementation

Question

I have implemented the string search algorithm using the naive method to count the number of times a substring occurs in a string. I did the implementation in javascript and python.

Algorithm (From Topcoder):

function brute_force(text[], pattern[]) 
{
  // let n be the size of the text and m the size of the
  // pattern
  count = 0
  for(i = 0; i < n; i++) {
    for(j = 0; j < m && i + j < n; j++) 
      if(text[i + j] != pattern[j]) break;
      // mismatch found, break the inner loop
    if(j == m) // match found
        count+=1
  return count
  }
}

Javascript Implementation:

a = "Rainbow";
b = "Rain";
count = 0;
function findSubStr(Str, SubStr){
    for (i = 0; i<a.length; i++){
        //document.write(i, '<br/>');
        for (j = 0; j < b.length; j++)
            //document.write('i = ',i, '<br/>');
            //document.write(j, '<br/>');
            if(a[i + j] != b[j]) break;
            document.write('j = ', j, '<br/>')
            //document.write('i = ',i, '<br/>');
    if (j  == b.length)
        count+=1;
    }
    return count;
}
document.write("Count is ",findSubStr(a,b), '<br/>');

Python Implementation:

a = "Rainbow"
b = "Rain"
def SubStrInStr(Str, SubStr):
    count = 0
    for i in range(len(Str)):
        for j in range(len(SubStr)):
            print j
            if (a[i + j] != b[j]):
                break
        if (j+1 == len(SubStr)):
            count+=1
    return count
print(SubStrInStr(a, b))

Now my question is for the line that implements if (j == b.length): It works well in javascript but for python I need to add 1 to the value of j or deduct 1 from the length of b. I don't know why this is happening.

okorkut · Accepted Answer · 2016-05-25 08:50:22Z

3

for x in range(4)

Unlike Javascript in Python for loop is used for every element in the list. Last value x will take is the last element of the list [0, 1, 2, 3] which is 3.

for(x = 0; x < 4; x++)

In Javascript x will take value for 4 and the loop will end because x < 4 condition no longer can be applied. Last value x will take is 4.

answered May 25, 2016 at 8:50

okorkut

5213 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tolu Ajayi Over a year ago

Thanks, well understood now

Iulian Popescu · Accepted Answer · 2016-05-25 08:43:28Z

1

You have this confusion because your code isn't identical. Executing for (j = 0; j < b.length; j++) the final value for j will be b.length (in case that b is a substring of a), but for Python, things are a little bit different. Running range(len("1234")) will result in [0, 1, 2, 3], so your for is more like a foreach, j storing the last value from the array and this is the reason why you have to add one. I hope that I was clear enough. If not, please ask for details.

answered May 25, 2016 at 8:43

Iulian Popescu

2,6434 gold badges25 silver badges31 bronze badges

1 Comment

Tolu Ajayi Over a year ago

Thanks Lulian I understand better now

NiteshCoder · Accepted Answer · 2021-01-05 15:59:53Z

I don't know about javascript , But I have implemented naive search in Python with all the cases with easiest way.

Take a glance on it as below. It will return no of time pattern got found.

def naive_pattern_search(data,search):
n = len(data) #Finding length of data
m = len(search) #Finding length of pattern to be searched.

i = 0
count = c = 0 #Taking for counting pattern if exixts.
for j in range(m-1):#Loop continue till length of pattern to be Search.
    while i <= (n-1):#Data loop
        
        #if searched patten length reached highest index at that time again initilize with 0.
        if j > (m-1):
            j = 0
        
        #Data and search have same element then both Index increment by 1.
        if data[i]==search[j]:
            #print(f"\n{ data[i] } { search[j] }")
            #print(f"i : {i}  {data[i]}   j : {j}  {search[j]}")
            i+=1
            j+=1
            count+=1
            
            #If one pattern compared and found Successfully then Its Counter for pattern.
            if count== (m-1):
                c = c + 1
        #Initilise pattern again with 0 for searching with next element in data.
        else:
            j = 0 #Direct move to 0th index.
            i+=1
            count=0 #If data not found as per pattern continuously then it will start counting from 0 again.

#Searched pattern occurs more then 0 then its Simply means that pattern found.
if c > 0:
    return c;
else:
    return -1;

Input : abcabcabcabcabc Output: Pattern Found : 5 Times

sos_dan · Accepted Answer · 2016-05-25 09:45:49Z

-1

I find your python implementation has some problem. If you set the b = "raiy", the function will incorrectly return 1. You may misunderstand the edge condition. Those two condition statements should be in the same level.

a = "Rainbow"
b = "Rain"
def SubStrInStr(Str, SubStr):
   count = 0
   for i in range(len(Str)):
       for j in range(len(SubStr)):
           # print (j)
           if (a[i + j] != b[j]):
               break
           if (j+1 == len(SubStr)):
               count+=1
return count
print(SubStrInStr(a, b))here

edited May 25, 2016 at 9:45

answered May 25, 2016 at 9:25

sos_dan

13 bronze badges

1 Comment

Tolu Ajayi Over a year ago

Thanks, I just found that out now, but how is it that it works in javascript even when the two if conditions are not at the same level.

Collectives™ on Stack Overflow

String Search Algorithm Implementation

4 Answers 4

1 Comment

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related