Calculating sum of similarities of strings
I think you need a suffix tree.

Its a data structure that puts all the prefixes of a string in a tree. This makes a number of operations faster, and I think you can make your similarity metric qualify.