The trie seems like a very good idea for your constraints.
A “thinking outside the box” alternative:
If you can afford some probability of answering “present” for a string that is absent
EDIT: if you can afford false positives, use a Bloom filter as suggested by WizardOfOdds in the comments.
For k=1, a Bloom filter is like a hash table without the keys: each “bucket” is simply a boolean that tells if at least one input with the same hash was present. If 1% false positives is acceptable, your hash table can be as small as about 100 * 20 million bits or roughly 200 MiB. For 1 in 1000 false positives, 2GiB.
Using several hash functions instead of one can improve the false positive rate for the same amount of bits.