字符串相似度计算是查找两个字符串的公共子串，利用公共子串的长度根据相应的公式来衡量两个字符串的相似程度。字符串相似度计算算法很多，如LCS算法、Levenshtein Distance算法、Heckel算法、GST算法等。对于历经N次笔试面试的人来说，这个再熟悉不过了。应要求，要帮忙写个计算两字符串相似度的算法，所以我特意去看了篇论文，并据此实现LCS与GST算法。
1. 概念
LCS（最长公共子序列）算法是将两个给定字符串分别删去0个或多个字符，但不改变剩余字符串的顺序后得到的长度最长的相同字符序列。给定字符串P、T、X，X称为P和T的最长公共子序列是指X是P和T的公共子序列，且对于P和T的任意公共子序列W，都有W<=X。
GST（Greedy String Tiling）算法是一种贪婪串匹配算法，这一算法对两个字符串进行贪婪式搜索以找出最大公有子串，它需要对要计算的两个字符串进行多次搜索，每次找出当前字符串中未“标注”部分的最长公共子串，并把找出的最长公共子串“标注”为已使用，避免最大匹配重复使用。
以“abcdefghijklmuvwxyz”与“ijkabclmdefghpq”为例解释GST的搜索过程：
（1）假如我们设最小匹配长度为2。第一次搜寻过程，先找到abc，此时最大匹配长度是3，之后找到defgh，因此它的长度大于3，所以此时最大匹配长度5，之后找到ijk，由于其长度小于5，放弃，最后是lm，其长度同样小于当前最大匹配长度5，放弃。
（2）将（1）中找到的最大匹配子串”标注为已使用“，重复（1）的过程，不过不再对”已标注子串“搜索，直到（1）中找到的最大匹配子串的长度为设置的最小匹配长度。
2. 应用场景
从上面的介绍中，可以看出LCS与GST的一个重要区别就是LCS得到的最大公共子串是严格有序的，对于一些顺序调换的情况，它计算出的相似度是比较低的，相反，GST并不要求其子串严格有序，只有存在相等子串，及时位置不对也可找到，因此相对来说，它计算出的相似度更高。
在分析生物学领域，DNA分子常被表示成一个字符串，两个DNA分子之间的相似性常用它们共同包含的碱基对的序列长度来度量，这是最长公共子序列应用最广泛的领域，LCS还可以应用于数据压缩、文件比较、语言识别等方面。GST算法在信息检索、文本编辑、信息提取等领域有重要的应用。
