1. 25

OpenBSD imported a very nice efficient algorithm from musl libc, here is the paper Two-Way String-Matching - Maxime Crochemore and Dominique Perrin.

  1. [Comment from banned user removed]

    1. 11

      This is about as good as it gets for tricky algorithmic code.

      It’s never readable at a glance if you don’t have all the details of the algorithm in your head, but with a description of the algorithm at hand you can pretty much read the code from top to bottom and it makes sense.

      I personally am not ok with things like for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--);, but besides that it seems fine.

      1. 10

        The posted rust equivalent looks just as complicated IMO. Though it is, arguably, better commented.

        1. 4

          Indee, and it has meaningful variable names. I love meaningful variable names, they make it so much easier to map variables to their meaning.

        2. 8

          I’d be curious to see the rust equivalent.

          1. 8

            This appears to be the rust stdlib implementation of the two-way algorithm.

            1. 9

              Hm, I find the C version far easier to read.

              1. 3

                Me too.

          2. 6

            This is straightforward code, it’s very easy to read.