I need a way of recognising that a character isn't in the map, but I don't want to use zero, since we will have needs for that for sentinels.

The current wrapper

struct cstr_exact_matcher
{
    exact_next_fn next;
    exact_free_fn free;
    cstr_sslice x, p;
};

with polymorphism works for searches where we have x and p up front, but not as well for cases where we preprocess x, such as suffix trees and suffix arrays. A uniform interface would be better.

Right now, it is pretty difficult to dispatch correctly on them. I would need a copy of each type.

With code such as

#define CSTR_SLICE_STRING(STR)                                               \
  _Generic((STR),                                                            \
           char *                                                            \
           : CSTR_SLICE((uint8_t *)STR, (long long)cstr_strlen(STR)),        \
           const char *                                                      \
           : CSTR_SLICE((const uint8_t *)STR, (long long)cstr_strlen(STR)))

the issue is that if STR is const char *, it won't be cast to a non-const, but the type checker will still complain that it would be in the first branch.

The alphabet always adds the sentinel to inter slices but never to string slices and it assumes that the slice it builds the alphabet from doesn't contain the sentinel. This needs to be more consistent to be easy to use.

What I have now is a mess I hacked up in an afternoon as an example to a student. It isn't fit to work as example code, and I need to clean it up.

Just get the O(m log n) version done for now. The O(m + log n) can come after all the GSA exercises.

Once I figure out how to use attributes to properly track resources in the static analyser (and once linters can understand C23), I want to get them back again. Right now, I have to leave the code annotation free. There is too much hassle, and I can't get it to work 80% of the time anyway.

Add tests that check that all exact marchers find the same matches