Custom indexOf for strings javascript with regex

Question

I was wondering how efficient my code is creating custom indexOf for strings in JavaScript using regex instead of looping with a for statement the whole way in most solution I find and I believe this got \$O(1)\$ since no loop is needed.

The idea is to use regex that put either the key or any list of word that is not key; this way I know that the value will be either in arr[0] or arr[1]. I also check using regex earlier whether the key exist in the value or not; this way I created non-looping indexOf with regex. This way I just return 0 if the key is in arr[0] or arr[0].length if it not in arr[0].

function findindex(value,key){
  let regex = RegExp( "((?!"+key+").)+|"+key , "ig" ); //regex for separating keys in the array
  let regex2 = RegExp(key,"ig");  // regex for checking if the key is exist in the value or not

  //first check before looping whether key is available in array or not
  if( !regex2.test(value) || value.length < key.length ){
    return -1;
  }

  let arr  = value.match(regex); //make an array  

  //alternative with condition statement
  return ( arr[0] === key || regex2.test(arr[0]) ) ? 0 : arr[0].length; 
}

Answer 1

Too sad, it's not O(1). There is a cost for:

• Constructing the regex into a DFA
• Calling test() or match() on the regex for the value

Complexities:

• A well implemented regex construction will be O(M) where M is the length of the key.
• While test/matching it afterwards will be O(N) where N is the length of the value. (best case, e.g. regexes with backtracking can result in horrible complexities)

So a couple of improvements can be:

• if the key is always the same. Construct the regex for the key only once.
• first start with comparing the length of the value and key before calling the more expensive test()-match() methods.

• apart from that, the idea of a regex is ok but I don't know if it's the most understandable way of writing an indexOf.

• Reference: Regex Complexities on SO