一种获取字符串最长公共子串的方法

摘要

本发明涉及一种获取字符串最长公共子串的方法，为了提高字符串之间最长公共子串的获取效率，本发明方法首先对某个匹配字节的两侧进行双向比较，得出初步公共子串，计算其长度；其次在当前的最长公共子串长度的基础上，结合多种跨越机制以试图找到更长的公共子串，循环往复，直至字符串遍历完毕。采用本发明，能够提高最长公共子串获取的计算效率，并减小资源开销。

主权项

一种获取字符串最长公共子串的方法，其特征在于，依次包括如下内容：A、接收单元接收待处理的两个字符串，将字符串分别命名为S1 和S2，假定S2为被比较字符串；B、预处理单元对S2进行预处理遍历，建立两个面向字符和连续同值区间的索引；C、基于S1当前的字符，查找S2的预处理索引，发现相同的字符后，跨越S2中不匹配字符直至匹配点；D、双向比较单元进行双向比较计算，找到基于当前匹配字符的公共子串，并计算其长度L；E、查找S2的预处理索引，判定是否还存在下一个与S1当前的字符相匹配的字符，若存在，则跨越至S2中下一个匹配点，重复步骤D、E；若不存在，则步骤C中S1的计算点跨越至当前的字符序号加上(L+1)的位置，重复步骤C、D、E，通过第一判断单元将更长的公共子串代替已有的最长公共子串，循环存入存储单元，直至通过第二判断单元判断S1遍历完毕；获得两个字符串的最长公共子串，经输出单元输出。