Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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