I like using [?]jellyfish[?] for counting kmers. It's pretty fast.

I would start with looking at Tallymer, which is a part of genometools. Tallymer will allow you to create a persistent index from one set and compare the occurrence ratio of k-mers from another set. I do a lot of k-mer work, and this is a great program that is well-documented.

Vmatch is a really powerful and versatile tool for any sequence comparison task. While I have never used it, the Unwords software seems like it might be the right tool for this job. These two software packages are related (same author) though, based on the Unwords publication, the data structures utilized by Unwords are completely different from Vmatch.

To add one more, I occasionally use meryl, which is really fast. This one has almost no documentation and I always have to read the C code to figure out the invocation, that is why I listed it last (not to say it's inferior, but you'll get going a lot faster with the other tools).