Is there some fast algorithm to check substrings in two string sets

user_2986034 0
Viewed 98

There is two string set (c++)

set<string> set1, set2;

I need to iterate set1 to check if any string in set1 is substring of string in set2.

Code below is my solution, is there any fast algorithm?

for(auto& str1 : set1) {
    for(auto& str2: set2) {
        if (strstr(str2.data(), str1.data()))
           // do something
    }
}

There are some restrictions

  1. this function is used in online RPC servers
  2. candidates of set2 and set1 may be too large to be loaded in memory entirely, so I can't build some index like trie or cache result.
algorithm c++ string
2 Answers

Suffix tree would be faster, O(n + m) where n is total length of all strings in set1 and m in set2, your set approach would be O(n*m*min(n,m)) in worst case, suffix array also uses linear memory.

If it does not fit into RAM you can consider splitting it up into "chunks" that fit and then checking all pairs of "chunks" from set1 against set2 and building suffix tree on them.

Also if hardware has SSD, virtual memory is also quite fast nowadays

user_40591450

Since you are interested whether there are any elements matching the criteria, then you could break from the cycle when the first is found. That's one obvious performance optimization.

user_4365600
Related