News for hackers. Stuff that matters.
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by mlyle on Friday January 22, 2021 @01:31PM (#25874541)
Note that the use of CMBC here was not thorough enough to spot that his reference implementation reads past the end of the string.
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by shric on Friday January 22, 2021 @01:37PM (#25874593)
I don't think it does, assuming the passed len is correct.
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by mlyle on Friday January 22, 2021 @02:01PM (#25874880)

        for (unsigned i=0; i<len; i++)
        {
                if (s[i]=='o' && s[i+1]=='k')
                        return i; // found
        };

The last iteration of this loop, it accesses s[len-1] and s[len]. If the string is null terminated, that's OK. If it's really just a length qualified string, that's not OK.

The later implementations treat len differently.

EDIT: It's worse than I said. The later version won't detect "ok" at the end of the string, because they are off by one in the OPPOSITE direction.

Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by shric on Friday January 22, 2021 @02:07PM (#25874969)
A string in C is, by definition, null terminated.
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by billsnow on Friday January 22, 2021 @02:15PM (#25875078)
Oh I have some bad news for you, buddy.
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by mlyle on Friday January 22, 2021 @02:09PM (#25874986)
Then why are we providing a length? Plenty of string-handling functions in the c standard library result in no terminating null if max length -- e.g. strncpy.

Note the second function is off by one in the opposite direction-- it doesn't find "ok" in "ok".

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.

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
Re:Knuth-Morris-Pratt string-searching algorithm: DFA-less v... by makapuf on Friday January 22, 2021 @02:51PM (#25875518)
Thats why strncpy is deprecated for strlcpy.