CODEWITHSUNDEEP
javascript
Ronak07
Ronak07

Reputation: 894

Optimised way to solve naive string search problem in javascript?

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 ?

Upvotes: 3

Views: 212

Answers (2)

vijaykumar Mahendran
vijaykumar Mahendran

Reputation: 37

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

Upvotes: 1

Mos&#232; Raguzzini
Mos&#232; Raguzzini

Reputation: 15831

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.

Upvotes: 3

Related Questions