Optimised way to solve naive string search problem in javascript?

Question

I have implemented the naive String search problem but I want to know what can be the alternate way to solve this algorithm ?

Here is my example :-

function naiveSearch(long, short) {
    let count = 0;
    for (let i=0;i<long.length;i++) {
        for(let j=0;j<short.length;j++) {
            if (short[j] !== long[i+j])
            break;
        if (j === short.length - 1)
        count++;
        }
    }
    return count;
}

As you can see the Time Complexity of this code is O(n ^ 2) as i have used the nested loop. So what can be the another way to solve this algorithm which will reduced the Time complexity ?

Thanks @Ry- for the reference, I understood the cases of naive search algorithm — Ronak07
– Ronak07, Commented Dec 23, 2019 at 15:03

Mosè Raguzzini · Accepted Answer · 2019-12-23 15:28:24Z

3

Naive search is inefficient by definition:

From wikipedia:

A simple and inefficient way to see where one string occurs inside another is to check each place it could be, one by one, to see if it's there

In JS there are simpler and more readable solution as:

function checkOccurrencies(string, stringToBeFound) {
  let counter = 0; 
  let found = string.indexOf(stringToBeFound, 0);

  while(found !== -1){
    counter += 1;  // Update number of match
    found = string.indexOf(stringToBeFound, found+1);  // Update found with next occurrence check
  }
  return counter;
}

console.log(checkOccurrencies("aababbajackasdasdjackasdhasdjack", "jack"));

Here are some benchmark with naive implementation vs indexOf It seems that the latter is also the more performant.

edited Dec 23, 2019 at 15:28

answered Dec 23, 2019 at 15:14

Mosè Raguzzini

15.9k1 gold badge34 silver badges46 bronze badges

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

1 Comment

Ronak07 Over a year ago

Thank you so much -Mosè Raguzzini

vijaykumar Mahendran · Accepted Answer · 2022-08-14 07:53:26Z

const Naivesearch = (string, pattern) =>{
  const patternLength = pattern.length;
  let count = 0;
  if(string.length > patternLength){
    for(i=0; i<string.length; i++){
      let final = string.substring(i, patternLength+i);
      if(final === pattern) count = count+1 ;
    }
    return count;
  }
  else return count
}


console.log(Naivesearch("akgjfjhuyutomatokajkhgsvkjrtomato", "tomato"))

const Naivesearch = (string, pattern) =>{
  const patternLength = pattern.length;
  let count = 0;
  if(string.length > patternLength){
    for(i=0; i<string.length; i++){
      let final = string.substring(i, patternLength+i);
      if(final === pattern) count = count+1 ;
    }
    return count;
  }
  else return count
}

console.log(performance.now())
console.log(Naivesearch("akgjfjhuyutomatokajkhgsvkjrtomato", "tomato"))
console.log(performance.now())

Collectives™ on Stack Overflow

Optimised way to solve naive string search problem in javascript?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related