目前许多信息都以文本的形式存放在计算机中,所以基于文本的信息检索技术,如最长公共子串匹配问题一直是文本管理、程序分析等领域的经典问题,长期以来受到广泛地关注与研究。然而最长公共子串的要求过于严格,在实际应用中,两个局部非常相似的文本其中的公共部分往往不是完全精确匹配的,因此需要提供支持近似匹配的最长公共子串匹配方法。目前尚未有相关技术的报道。因此,本文重点研究支持编辑距离约束的近似最长公共子串匹配问题。本文首先综述了现有的字符串近似匹配技术,并基于此,提出了一种基于动态规划的算法,这个算法首先用最长公共子串的动态规划算法求出公共子串,再用编辑距离和最长公共子序列的动态规划方法,计算具有公共前缀的子串组成的比对区域,找到所有支持编辑距离约束的近似公共子串,最后进行长度验证找到支持编辑距离约束的近似最长公共子串。该算法可以保证O(kmn)的时间复杂度。为了进一步提高算法的效率,本文提出了基于后缀数组的公共子串匹配优化算法。该算法先采用后缀数组的方法求出所有公共子串,再将相邻连接距离不大于编辑距离阈的公共子串连接起来构造验证集,在构造验证集的过程中采用了基于公共子串位置和基于公共子串间距离的过滤策略,最后用启发式的方法在验证集中找出支持编辑距离约束的近似最长公共子串,提高了查询效率。最后,本文在三个不同的真实数据集上测试了这两种算法的性能,基于动态规划的算法,由于需要对所有具有相同前缀开始的比对区域进行动态规划计算,所以算法的性能比基于公共子串的查询算法差。实验发现,基于公共子串的算法由于采用了基于公共子串位置和公共子串间距离的过滤技术,所以该算法的性能跟两个串的公共子串的个数和长度有关系,如果公子串个数比较少,且长度都比较长,算法的性能越好。