# Faster algorithm to search in a set of strings

Suppose that we are given a pattern $p$, which is a set of characters (order doesn't matter). We are also given a set of strings $A$. I want to find all of the strings in $A$ whose characters are all contained in $p$ (without taking the order of these characters into consideration), i.e., to find all $s \in A$ such that every character in $s$ is also in $p$.

The algorithm that I use is to loop every string in $A$ first, and, then, loop every character in each string, so the time complexity is $O(nm)$. My question is: is there any faster algorithm? Bit operation or matrix is ok.

Here is an example:

Pattern "abcdef"

Set A  {a, b, ac, ag, bde, cbd, daf, cg, abzdef, d}

Desired results : a, b, ac, bde, cbd, daf, d

Filtered: ag, cg, abzdef (as g,z don't belong to the original string "abcdef")

• What exactly is $n$ and $m$? – Mario Cervera Feb 23 '17 at 9:50
• @Mario Cervera : just my wild guess, but I'm taking the O(nm) mentioned in the OP's question is alluding to n = size of A and m = max(length(s)) for all s in A. – YSharp Feb 26 '17 at 3:09
• a pattern p, which is a set of characters (order doesn't matter) - so why call it pattern in the first place? – greybeard Apr 27 '17 at 10:19

You only need to read the strings in set $A$ and the characters in pattern $p$ once. You can store each character of $p$ in a hash table* for (expected) constant time lookup, and, then, perform a linear scan in $A$ to obtain the desired result. The running time of this solution is $O(n+m)$, where $n$ is the length (i.e., the total number of characters) of $A$ and $m$ is the length of $p$.
* A solution that is more space-efficient than the hash table (and guarantees constant time lookup) is to use a bit array $P$ to store pattern $p$. This array will be indexed by the ASCII values of all possible characters that you want to consider in your application; for instance, $P$ will have 26 index positions in the case of the English alphabet: one per distinct character. The $i$-th bit of $P$ will be set to $1$ if the $i$-th character appears in $p$, and to $0$ otherwise. Thus, you can scan $A$ in linear time and discard every string that contains at least one character $c$ such that $P[v_c]=0$, where $v_c$ is the ASCII value of $c$.