Thanks, the idea of saving time by looking at imperfect matches first to reduce the number of comparisons needed will definitely save time.
The larger file will be actually the same from one run to another, so yes, I've thought of storing either the sorted file (if I go with a Unix-like approach like comm or uniq) or the bitvector for that file to do it only once and save time in the subsequent runs.
The strings are pretty random.