What if you take one list of strings and convert it to a HoHoHo...?
The top level key would be the first letter of each string. At each level, you have either the string to eq against, or a hash of choices for the next letter.
EG:
my $tree =
{f =>
{o => 'foo',
i =>
{r => 'fire',
n => 'fine',
},
},
b => 'bar',
}
You would know instantly that 'monk' isn't in the second list because !exists($tree->{m}).
You would know 'balloon' doesn't exist pretty quick because exists($tree->{b}) and ref($tree->{b}) ne 'HASH' and $tree->{b} ne 'balloon'.
If the second list is something constant without too much duplication early in the string, such as a dictionary, then it should work really well.