The fastest C++ algorithm for string testing against a list of predefined seeds (case insensitive)

Question

I have list of seed strings, about 100 predefined strings. All strings contain only ASCII characters.

std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"}; 

My app constantly receives a lot of strings which can contain any characters. I need check each received line and decide whether it contain any of seeds or not. Comparison must be case insensitive.

I need the fastest possible algorithm to test received string.

Right now my app uses this algo:

std::wstring testedStr; for (auto & seed : seeds) {     if (boost::icontains(testedStr, seed))     {         return true;     } } return false; 

It works well, but I'm not sure that this is the most efficient way.

How is it possible to implement the algorithm in order to achieve better performance?

This is a Windows app. App receives valid std::wstring strings.

---

Update

For this task I implemented Aho-Corasick algo. If someone could review my code it would be great - I do not have big experience with such algorithms. Link to implementation: gist.github.com

Answer 1

If there are a finite amount of matching strings, this means that you can construct a tree such that, read from root to leaves, similar strings will occupy similar branches.

This is also known as a trie, or Radix Tree.

For example, we might have the strings cat, coach, con, conch as well as dark, dad, dank, do. Their trie might look like this:

A search for one of the words in the tree will search the tree, starting from a root. Making it to a leaf would correspond to a match to a seed. Regardless, each character in the string should match to one of their children. If it does not, you can terminate the search (e.g. you would not consider any words starting with "g" or any words beginning with "cu").

There are various algorithms for constructing the tree as well as searching it as well as modifying it on the fly, but I thought I would give a conceptual overview of the solution instead of a specific one since I don't know of the best algorithm for it.

Conceptually, an algorithm you might use to search the tree would be related to the idea behind radix sort of a fixed amount of categories or values that a character in a string might take on at a given point in time.

This lets you check one word against your word-list. Since you're looking for this word-list as sub-strings of your input string, there's going to be more to it than this.

Edit: As other answers have mentioned, the Aho-Corasick algorithm for string matching is a sophisticated algorithm for performing string matching, consisting of a trie with additional links for taking "shortcuts" through the tree and having a different search pattern to accompany this. (As an interesting note, Alfred Aho is also a contributor to the the popular compiler textbook, Compilers: Principles, Techniques, and Tools as well as the algorithms textbook, The Design And Analysis Of Computer Algorithms. He is also a former member of Bell Labs. Margaret J. Corasick does not seem to have too much public information on herself.)