How to do high performance string matching when comparing unordered sets of tokens
So you want to use the Jaccard index as your metric of similarity.  Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs.  For instance, you can use locality-sensitive hashing.  Hint for the future: you might want to do more research in the future based on feedback from folks, as locality-sensitive hashing was already suggested in the comments and a relevant Wikipedia page was also mentioned in the comments.

If tokens are not too common, there's another alternative method you could also try.  You could build an inverted index: an index that, for each token, lists all of the strings that contain it.  Now given a new string S, it's easy to enumerate over all of the tokens in it, look each one up in the inverted index, find all other strings that share at least one token in common with S, compute the similarity between that string and S, and keep the best one.  As long as no string contains too many tokens and no token is present in too large a fraction of strings, this will perform better than all-pairs comparison.



Your "extended" problem is different in nature and would probably be better asked as a separate question.  It might be a much harder problem.