3 ms·

There are a bunch of test cases here: https://github.com/microsoft/STL/pull/724/commits/a7da5cce8c75a8a54c58eeeb4d645a561e7ab4e2#diff-52bfd6b8a11ca695a37a51fc6

There are a bunch of test cases here: https://github.com/microsoft/STL/pull/724/commits/a7da5cce8c75a8a54c58eeeb4d645a561e7ab4e2#diff-52bfd6b8a11ca695a37a51fc60dfc1c0 https://github.com/microsoft/STL/pull/724/commits/a7da5cce8c... Looks like it can happen with quite small needles, eg. "aa".

StephanTLavavej 7y ago
After comparing the outputs of the old and new algorithms, I believe that a needle needs more than two repeats in order to trigger the bug. That is, "aa" and "abab" don't trigger the bug, but "aaa" and "ababa" do, the last one having a partial third repeat (needle "ababa" with haystack "WXYZababa" was definitely wrong). I tested the table output for "aa" for completeness (and just in case we manage to damage it in the future). Disclaimer: I don't understand the algorithms deeply enough to write them from scratch, and I'm writing this at 6 AM.