Infix search in millions of strings Let's say we have millions of strings (each of them &lt; 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.