Skip to content

Instantly share code, notes, and snippets.

@phillipberndt
Created September 10, 2016 21:09
Show Gist options
  • Save phillipberndt/2fd22acf6daefc204eb3b5051358d778 to your computer and use it in GitHub Desktop.
Save phillipberndt/2fd22acf6daefc204eb3b5051358d778 to your computer and use it in GitHub Desktop.
Haystack: babaacb
Needle: abab
Split into [ "babaa", "b" ]
> Match the longest substring with the input and keep track of the longest match.
> If you don't get a complete match, use the longest one to slice up the
> substring once more, and retry with the next longest substring.
There's no complete match, and the longest match is "bab". So splice up the substring again, and retry with
[ "bab", "aa", "b" ].
"bab" matches, but then the left subproblem is unsolvable: The haystack part [] cannot match the needle part "a".
Now what??
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment