Supporting more types in Boyer-Moore about string-searching HOT 12 CLOSED

Yup, I'll make another issue for adding more algorithms.

from string-searching.

Hmm okay, support for types that follow 2 rules can be added:

• indexable
• length can be queried

That would include slices as well as vectors, I suppose.

from string-searching.

Implemented in 15a7ec2

from string-searching.

Yup, this is definitely a feature worth having. However, arbitrary types can't be supported as all possible elements of the type (in the case of u8 there are 256 possible elements) need to be known in order to add them to the bad character table.

from string-searching.

I'd suggest supporting all integer (signed and unsigned, or maybe just unsigned?) types.

from string-searching.

Oh, sorry! I forgot about the limitations of the algorithm. :(
Knuth–Morris–Pratt algorithm is more suitable for any type.

Just an idea: rename this repository to zig-search-algorithms or something like this.
And add other popular algorithms.

from string-searching.

There is awesome String Matching Algorithms Research Tool but it is GPL-licensed.

from string-searching.

I think new name zig-string-searching is slightly incorrect now. :)
I suggest use zig-pattern-searching.

from string-searching.

Hmm, pattern kind of implies some regex-ish matching. According to Wikipedia, "string-searching algorithm" is the term for this family of algorithms.

from string-searching.

Sure, but structs are't strings (if new algorithms are added).

from string-searching.

I think that we want to limit the scope of this repository to slices of some type T, i.e. searching for a []const T in another []const T. This is basically equivalent to the mathematical definition of strings, which are finite sequences of symbols from an alphabet. The alphabet would be T in this case.

This does not prevent us from choosing some struct for T. We would have to include some equality function in that case because structs cannot be compared with the == operator anymore.

For example:

const Abc = struct {
    id: usize,
    some_data: []const u8,

    pub fn equals(self: Abc, other: Abc) bool {
        return self.id == other.id;
    }
};

We can then search for a []const Abc in a []const Abc if we want to.

from string-searching.

std.meta.trait.isIndexable now supports vectors.
So potentially, some algorithms could use this trait.
But I'm waiting when ziglang/zig#5443 will be merged.

from string-searching.