needle === haystack ?

[Niekes]

I don't get this part:

if (nlen === hlen) {
    return needle === haystack;
  }

this means: "apple" === "appel" false

Shouldn't this example return true?

Why is nlen === hlen important ?

[bevacqua]

it's an optimization shortcut

[pie6k]

I think I have to admit this was the best explanation of confusing part of the code I have ever seen in my entire life!

[pie6k]

I've decided to rewrite it as I consider code of this lib hard to understand and also I needed it to return informations about which parts were fuzzy and which were input

Maybe it'll be useful for someone (it's in typescript)

type MatchRoleType = 'input' | 'fuzzy' | 'suggestion';

interface FuzzyMatchData {
  content: string;
  type: MatchRoleType;
}

export interface FuzzyMatchOptions {
  truncateTooLongInput?: boolean;
}

export function fuzzyMatch(
  fuzzyInput: string,
  fullString: string,
  { truncateTooLongInput }: FuzzyMatchOptions = {},
): FuzzyMatchData[] | false {
  // input is longer than fullString and truncating is disabled
  if (fuzzyInput.length > fullString.length && !truncateTooLongInput) {
    return false;
  }

  // truncate if fuzzyinput is longer than fullstring
  if (fuzzyInput.length > fullString.length && truncateTooLongInput) {
    fuzzyInput = fuzzyInput.substr(0, fullString.length);
  }

  // both fuzzy and full string are equal - they match without being fuzzy
  if (fuzzyInput === fullString) {
    return [{ content: fuzzyInput, type: 'input' }];
  }

  const fuzzyMatchData: FuzzyMatchData[] = [];

  const leftFuzzyLetters = fuzzyInput.split('');

  let fuzzyLettersBuffer: string[] = [];
  let matchingLettersBuffer: string[] = [];

  function clearFuzzyBuffer() {
    if (fuzzyLettersBuffer.length > 0) {
      fuzzyMatchData.push({
        content: fuzzyLettersBuffer.join(''),
        type: 'fuzzy',
      });
      fuzzyLettersBuffer = [];
    }
  }

  function clearMatchingBuffer() {
    if (matchingLettersBuffer.length > 0) {
      fuzzyMatchData.push({
        content: matchingLettersBuffer.join(''),
        type: 'input',
      });
      matchingLettersBuffer = [];
    }
  }

  for (let fullStringLetter of fullString) {
    const currentFuzzyLetter = leftFuzzyLetters[0];

    console.log({ currentFuzzyLetter, fullStringLetter });

    // no more input
    if (!currentFuzzyLetter) {
      // clear buffers
      console.log('no more fuzzy letters');
      break;
    }

    // another fuzzy letter to add
    if (fullStringLetter !== currentFuzzyLetter) {
      // make sure to clean matching letters buffer if we have some
      clearMatchingBuffer();
      fuzzyLettersBuffer.push(fullStringLetter);

      continue;
    }

    // match!
    leftFuzzyLetters.shift();
    // clear fuzzy letters buffer
    clearFuzzyBuffer();

    matchingLettersBuffer.push(fullStringLetter);

    if (!leftFuzzyLetters.length) {
      clearMatchingBuffer();
    }
  }

  if (leftFuzzyLetters.length > 0) {
    return false;
  }

  const matchedPart = fuzzyMatchData.map((match) => match.content).join('');

  const suggestionPart = fullString.replace(matchedPart, '');

  if (suggestionPart) {
    fuzzyMatchData.push({ content: suggestionPart, type: 'suggestion' });
  }

  return fuzzyMatchData;
}

[edit] Actually - I've published it to npm because true/false result was not enough for my case - https://github.com/pie6k/fuzzystring