Try using aho-corasic with a treap (as a goto map).