Let's say we have millions of strings (each of them < 100 characters):
alpha allo blah hello world orlando ...
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"
is that called "infix search"?
I'm looking for something working on strings even without meaning (the pattern
qysshould allow to find the string
uyiuqysidiamong millions of other strings), on DNA (pattern
GGATCATTGAAGG), on sequences (subsequence
1, 4, 8found in sequence
7, 2, 1, 4, 8, 19, 32), etc.