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

• albert cahyawan: I do agree that this not a really understandable way of writing indexOf, just though I could make it faster by reducing the loop. As I just learned regex I though it's a cheap way to avoid looping to get a value. never thought calling test() and match() is really expensive. thanks a lot for the suggestion
• Sam Segers: I wouldn't say "really expensive", in general it will be quite similar to a normal loop. And far better than a naïve implementation using 2 loops with worst case O(NM). You can have a look at some popular string search algorithms like "Rabin-Karp", "Boyer-Moore" or my favourite "Knuth-Morris-Pratt" that is construction a DFA and using it which can give you more insights in this topic.