5
\$\begingroup\$

The task

was initially solved here, but was too buggy:

Given a string and a pattern, find the starting indices of all occurrences of the pattern in the string. For example, given the string "abracadabra" and the pattern "abr", you should return [0, 7].

My solution

Tried to solve it using KMP-algorithm:

function findStartingIndex(T, pattern) {
  if (pattern.length > T.length) { return []; }

  let next = 0;
  const res = [];

  const check = i => {
    for (let j = 1; j < pattern.length; j++) {
      if (next <= i && T[i + j] === pattern[0]) { next = i + j - 1; }
      if (T[i + j] !== pattern[j]) { return false; }
    }
    if (next <= i) { next = i + pattern.length - 1; }
    return true;
  };

  for (let i = 0; i < T.length; i++) {
    if (i + pattern.length > T.length) { return res; }
    if (T[i] === pattern[0] && check(i)) { res.push(i); }
    i = next;
  }
  return res;
}
\$\endgroup\$
2
  • \$\begingroup\$ Did you write automated tests? Which are your test cases? As you saw in the previous question, a single test case is not enough. If you only had this single test case, the expression (() => [0, 7]) would satisfy all test cases, even though it is clearly wrong. \$\endgroup\$ May 31, 2019 at 22:32
  • \$\begingroup\$ @RolandIllig Nope, I didn't write automated tests. But maybe I should in the future. I only tested some cases that I thought were critical: abracadabra | abr, banana | a, 12121212 | 1212, 1111 | 1 \$\endgroup\$ May 31, 2019 at 22:39

1 Answer 1

2
\$\begingroup\$

A quick review;

  • This tends to find more than 1 index, findStartingIndex -> findStartingIndexes
  • In KMP, T is a lookup table, not the source string
  • If you used the while statement proposed by Wikipedia, you would not need the first if statement
  • In KMP, they use a lookup table, your code does not
  • You have a tendency to one line if statements, it hampers readability
  • Your code does not actually work findStartingIndex("abracadabra","abr") goes into an infinite loop, next doesn't get updated, and so keeps getting reset to 2
  • I wrote a counter proposal, it does use a bit of optimization but it does not use a search table like KMP, and is in my opinion far more understandable/readable

function findStartingIndexes(haystack, needle){
  
  const needleLength = needle.length;
  const searchSpace = haystack.length - needleLength;
  const indexes = [];
  let position = 0;
  
  while(position <= searchSpace){
    if(haystack[position] == needle[0] &&
      haystack.slice(position, position + needleLength) == needle) {
          indexes.push(position);
      }
    position++;
  }
  return indexes;
}

function findStartingIndex(T, pattern) {
  if (pattern.length > T.length) { return []; }

  let next = 0;
  const res = [];

  const check = i => {
    for (let j = 1; j < pattern.length; j++) {
      if (next <= i && T[i + j] === pattern[0]) { next = i + j - 1; }
      if (T[i + j] !== pattern[j]) { return false; }
    }
    if (next <= i) { next = i + pattern.length - 1; }
    return true;
  };

  for (let i = 0; i < T.length; i++) {
    if (i + pattern.length > T.length) { return res; }
    if (T[i] === pattern[0] && check(i)) { res.push(i); }
    i = next;
  }
  return res;
}

//Infinite loop ;(
//console.log("[0,2]",JSON.stringify(findStartingIndex("abracadabra","abr")));

console.log("[0,2]",JSON.stringify(findStartingIndexes("ababab","abab")));
console.log("[]", JSON.stringify(findStartingIndexes("","abab")));
console.log("[0,7]",JSON.stringify(findStartingIndexes("abracadabra","abr")));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.