Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters):

alpha
allo
blah
hello world
orlando
...


I know how a binary search tree or a trie can help to do "prefix search" (example: find all strings that match al*, i.e. beginning with al).

Which data structure / algorithm could be used to search patterns inside a word (i.e. not necessarily at the beginning or end), that wouldn't need to do an inefficient O(n) traversal of all the millions of strings?

Example: the pattern orl should match "hello world" as well as "orlando"

Notes:

• is that called "infix search"?

• I'm looking for something working on strings even without meaning (the pattern qys should allow to find the string uyiuqysidi among millions of other strings), on DNA (pattern ATTG found in GGATCATTGAAGG), on sequences (subsequence 1, 4, 8 found in sequence 7, 2, 1, 4, 8, 19, 32), etc.

Let $\$$be a symbol not in the alphabet, and let$\{ w_i \}_{i \in \mathbb{N}}$be the strings you are searching from. Construct the string$S = w_1 \circ \$\circ w_2 \circ \$ \circ \dots \circ w_n$and use Ukkonen's algorithm to construct a suffix tree for$S$. You are now able to retrieve all$m$occurrences of a pattern$P$in time$\Theta(m + |P|)$, with$\sum_i|w_i|$preprocessing time. • Thank you for your helpful answer. To make it even easier to understand, do you think you could add an example of suffix tree for alpha$allo$blah$hello world\$orlando to show how it would work to find for orl? – Basj Apr 20 '18 at 15:05
• Thank you for your answer. Could you add an example? I know what are equivalence classes in math, but how would you define it in this context? Thank you in advance if you can elaborate a bit on the bitmap of characters contained in the string, it looks promosing! I guess alpha would be 10000001000100010000000000? Do you mean you would pre-filter the strings which have the necessary characters first (using bitmap), and then perform a 2nd search (which kind of 2nd search?) – Basj Apr 20 '18 at 19:33