0

I am writing a function that takes two strings as input parameters: text and pattern.

  • If text ends with a substring starting at index index and this substring is a start of pattern, then return index.

  • If there is no such substring, return -1.

I've come up with the following function, but I wonder if there is more efficient solution.

So the question is: is there more efficient algorithm to find such substrings?

function findSubstring(text, pattern) {
  let index = -1;

  for (let i = 1; i <= text.length; i++) {
    const tail = text.substr(-i);

    if (pattern.indexOf(tail) === 0) {
      index = text.length - i;
    }
  }

  return index;
}

const exampleText = 'const result = items.m';
const examplePattern = '.map((item) => {})';

console.log(findSubstring(exampleText, examplePattern)); // -> 20
nrg
  • 518
  • 3
  • 7
  • 1
    Here is the rewrite of the accepted answer there to fit your needs: https://jsfiddle.net/7pqzh6j4/ – Kaiido Apr 15 '19 at 06:33
  • @Kaiido Thank you! It seems to be very close to what I am looking for. I'll check if this can be improved further based on my needs. – nrg Apr 15 '19 at 09:13
  • Note that @Jonas' answer is probably even faster, but won't behave the same as your code in some cases. – Kaiido Apr 15 '19 at 09:15
  • @Kaiido I think I'll end up writing a benchmark to compare the solutions to be completely sure. – nrg Apr 15 '19 at 09:23

1 Answers1

1

I'd check either for a partial match at the end or a full match before that:

  const last = text.lastIndexOf(pattern[0]);
  if(text.substr(last, last + pattern.length) === pattern.substr(0, text.length - last))
    return last;
  return text.lastIndexOf(pattern, last);

Although the underlying algorithm is probably less eficcient, this may still run faster due to engine optimizations, wether it is faster in your case needs to be tested.

Jonas Wilms
  • 132,000
  • 20
  • 149
  • 151
  • 2
    This will not return the same result on repeating input, take for instance `fn("abcabcabc", "abcabc")`, yours will return `6` (last index of the first `"abc"` sequence), while OP's will return `3` taking `"abcabc"` in full. – Kaiido Apr 15 '19 at 08:01