Your problem is very similar to protein sequence homology searches. A protein can be represented as nothing more than a string from an alphabet of 20 letters. Sequence homology searches (which are crucial to biology and bioinformatics) basically attempt to find and score similarities between two or more such sequences.

Various algorithms exist to do this e.g. Needleman and Wunsch (Journal of Molecular Biology 48 pp443) and the ever popular BLAST www.ncbi.nlm.nih.gov/blast Of course these solutions are designed for molecular biology and would require a lot of work to alter them to handle general strings. My guess is you are looking for a simpler solution...