Use Teddy algorithm to perform multiple substring string searches

[lpereira]

When calling the startswith() or endswith() method of a str object with a tuple of strings, we should use an algorithm that's better suited to match multiple strings in parallel rather than iterating over that tuple and checking for every since entry.

One such algorithm is the Teddy algorithm, used by the Hyperscan regex library, and Rust's aho-corasick crate. This algorithm exploits vector instructions to match multiple strings in parallel and is able to yield great performance when compared to the linear, scalar version.

[sweeneyde]

Don't these sorts of algorithms typically require building up a trie/suffix-tree or other pre-work? I'd worry that that would be much more expensive than the naive approach, especially for startswith/endswith, where the naive algorithm is already worst-case O(sum(map(len, prefixes))), the same cost as building the tree would be, but with the ability to short-circuit. Unless you'd plan to cache the data somewhere?

If there was some method like string.index_of_first({"foo", "bar", "baz"}) the trade-off might be different there, and Aho-Corasick might be the way to go.