Fast algorithm for finding out if a string contains any string in a given array

Question

I have a list of about 50 keywords and about 50000 strings. I check every string if it contains at least one of the keywords. I'm not interested in the matched keyword or the number of matched keywords. I only want a "true" or "false" back, as fast as possible.

So, I bet there's an algorithm out there that outperforms my current LINQ version by far:

class MyEnumerableExtension
{
    public static bool ContainsAny(this string searchString, IEnumerable<string> keywords)
    {
        return keywords.Any(keyword => searchString.Contains(keyword))
    }
}

bool foundAny = "abcdef".ContainsAny(new string[] { "ac", "bd", "cd" } );

Community · Accepted Answer · 2017-05-23 10:33:19Z

1

isn't this in essence the same as your other question of today Efficient algorithm for finding all keywords in a text except modified to return once a match has been found?

edited May 23, 2017 at 10:33

CommunityBot

11 silver badge

answered Nov 18, 2010 at 13:43

The Archetypal Paul

41.9k20 gold badges107 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

VVS Over a year ago

No it isn't. I have two separate concerns. One is finding all string containing any keyword in a list of given keywords. The other is tokenizing these found strings by using another keyword list. These lists are different and have different purposes.

The Archetypal Paul Over a year ago

OK, but the solution is the same algorthm in both places (altered in this case to return once one match is found)?

VVS Over a year ago

Whoops, I should have read until the end. I think you're right, I could modify the algorithm to return after a single keyword is found. Since I would have to build the keyword tree only once this should be a very fast solution.

Carra · Accepted Answer · 2010-11-18 13:42:15Z

0

There are multiple algorithms to search a text for a set of substrings.

answered Nov 18, 2010 at 13:42

Carra

18k8 gold badges66 silver badges75 bronze badges

Comments

Victor Haydin · Accepted Answer · 2010-11-18 13:42:33Z

0

Yo can implement Knuth-Morris-Pratt algorithm.

answered Nov 18, 2010 at 13:42

Victor Haydin

3,5582 gold badges28 silver badges41 bronze badges

1 Comment

The Archetypal Paul Over a year ago

That searches for one word. There are better algorithms for searching for any of a set. See Wikipedia en.wikipedia.org/wiki/…

Les · Accepted Answer · 2010-11-18 14:03:06Z

A quick analysis shows that you are iteratively searching for the keywords. If you could search in one pass for all fo the keywords, you should have an overall improvement in your algorithm. A Regex expression can do that and couple it with the "Compiled" option and you should begin to see a performance increase (because it will single pass the string for all keywords). But, it would only benefit you if you have several keywords. Here's a quick idea to help you along, but note, I have not actually tested the performance against your algorithm.

        string[] keywords = { "ac", "bd", "cd" };
        string[] tosearch = { "abcdef" };
        string pattern = String.Join("|", keywords);
        Regex regex = new Regex(pattern, RegexOptions.Compiled);
        foundAny = regex.IsMatch(String.Join("|", tosearch));

Also note, this works as long as your keywords do not contain any Regex special characters (and your search strings do not contain the pipe symbol. However, the special characters could be overcome with escape sequences, and the search strings do not have to be joined as I've done.

Collectives™ on Stack Overflow

Fast algorithm for finding out if a string contains any string in a given array

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related