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 stringuyiuqysidi
among millions of other strings), on DNA (patternATTG
found inGGATCATTGAAGG
), on sequences (subsequence1, 4, 8
found in sequence7, 2, 1, 4, 8, 19, 32
), etc.