0

I am trying to implement naive search and I do not get the expected result. Can anyone point out here, what could be the possible error.

function naive(string, str) {
    for (let i = 0; i <= string.length - str.length; i++) {
        if (string[i] == str[0]) {
            let counter = 1

            for (let j = 1; j <= str.length; j++) {
                if (string[i + j] == str[j]) {
                    counter++;
                    console.log(counter)
                } else
                    counter = 0;
            }

            if (counter == str.length) {
                console.log(`${counter} pattern matched at ${i}`)
            }
        } else
            console.log('nothing matched')
    }
}
Andreas
  • 21,535
  • 7
  • 47
  • 56
Mayank Nauriyal
  • 61
  • 6
  • Is what you want counting the number of occurences of a pattern in a string? – Baboo Aug 25 '18 at 12:48
  • yes exactly, I want it to print a message in console, everytime it comes across such patterb – Mayank Nauriyal Aug 25 '18 at 12:55
  • Have a look [here](https://stackoverflow.com/questions/4009756/how-to-count-string-occurrence-in-string) to count occurences using regex in 2 lines – Baboo Aug 25 '18 at 12:58
  • Please show how you are calling the function - what example arguments do you pass, what result did you expect to get, and what did happen instead? – Bergi Aug 25 '18 at 13:05
  • Thanks @Baboo_ I am practicing basics of computer science and you pointed out a new thing(atleast for me). – Mayank Nauriyal Aug 25 '18 at 13:08
  • Bergi I was implementing this in console of chrome :p and tested with some basic examples ('mayankananan', 'an'), I understood my mistake now. Thanks for asling though :) – Mayank Nauriyal Aug 25 '18 at 13:09

2 Answers2

2

var match_found = false;
function naive(string, str){
  for(let i =0; i <= string.length - str.length; i++){
      if(string[i] == str[0]){
        let counter= 1
            for(let j = 1; j < str.length; j++){
                if(string[i + j] == str[j]){    
                  counter++;
                }else{
                  break;
                }
            }
        if(counter == str.length){ 
          console.log('Pattern matched at ' + i);
          match_found = true;// can break; here if you wish to, else it will give you all matches present
        }
      }
  }
  if(match_found === false){
    console.log(str + ' not found in ' + string);
  }
}

naive('abcdgggabcdggg','ggg');

  • You increment the counter when there is a match, but you need to break the loop where there is a mismatch.

  • Your inner for loop condition needs to have j < str.length instead of j <= str.length, because index starts from 0.

  • else console.log('nothing matched'). You can't just instantly decide that. If a string index doesn't match, you need to still keep looking for the rest of the indexes. Best way to go about it is to maintain a boolean flag for it as shown in the above code.

nice_dev
  • 17,053
  • 2
  • 21
  • 35
1

You don't need to do all that iteration and comparison by yourself. Here's a simpler version of your function:

function naive(string, str) {
  var counter = 0, 
    i = string.indexOf(str, 0);  //find first occurance of str in string

  while(i !== -1){
    ++counter;  //we have a match, count one up
    console.log(`counter %i, index %i`, counter, i);
    i = string.indexOf(str, i+1);  //find next occurance 
  }
  return counter;
}

console.log("result", naive("lorem upsum", "m"));
Thomas
  • 11,958
  • 1
  • 14
  • 23