Knuth-Morris-Pratt string-searching algorithm: DFA-less version

Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by shric on Friday January 22, 2021 @02:20PM (#25875148)

Because the writer of the function doesn't want to bother to check the null terminator. I'm not saying it's a good function, it just doesn't have an issue as long as the input is a valid string with a correct length.

strncpy, despite what its name implies, does indeed not necessarily produce strings.

Regardless, a C string is defined to have a null terminator. All bets are off if you don't provide a string.

[ Parent | on HN ]

Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by mlyle on Friday January 22, 2021 @04:36PM (#25876614)

The issue is: the two functions that we're comparing for correctness treat lengths very differently: one scans len-1 bytes, the other scans len+1 bytes.

Even with a null terminator, there isn't a length that would work for both without overrunning the buffer.

        printf("%d %d\n", search_ok_1("mok", 2), search_ok_2("mok", 2));
        printf("%d %d\n", search_ok_1("mok", 3), search_ok_2("mok", 3));   /* Overruns without null term */
        printf("%d %d\n", search_ok_1("mok", 4), search_ok_2("mok", 4));   /* Overruns even WITH null term */

Prints out:

    1 2
    1 3
    1 1

[ Parent | on HN ]