Aho-Corasick
One automaton for the whole dictionary, one pass over the text, demoing the p/moul/x/daily/ahocorasick library.
The 1975 example
Patterns he, she, his, hers over ushers. Three of the four overlap, and hers ends where nothing else starts.
| start | end | pattern |
|---|---|---|
1 |
4 |
she |
2 |
4 |
he |
2 |
6 |
hers |
One pass over a sentence
Patterns the, he, fox, over, lazy over the quick brown fox jumps over the lazy dog.
| start | end | pattern |
|---|---|---|
0 |
3 |
the |
1 |
3 |
he |
16 |
19 |
fox |
26 |
30 |
over |
31 |
34 |
the |
32 |
34 |
he |
35 |
39 |
lazy |
5 patterns, 17 automaton nodes, 43 bytes read once, 7 matches. Running a single-pattern scan per word would read those bytes 5 times instead.
Scan your own text: append it to the path, for instance
/thermos, wheretheandheoverlap on the same three letters.
