3
\$\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\$
  • \$\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\$ – Roland Illig May 31 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\$ – thadeuszlay May 31 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.