2.1 最長公共子串算法與最小編輯距離算法的改進(jìn)最長公共子序列的定義是對(duì)于一個(gè)序列 S， 如果分別是兩個(gè)或多個(gè)已知序列的子序列， 且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。最長公共子序列問題是尋找兩個(gè)或多個(gè)已知序列的最長公共子序列。Wagner 等人提出了最長公共子序列（Longest Common Subsequence， LCS）問題后，基于 LCS 的應(yīng)用研究工作已經(jīng)取得了顯著成效。李占波等人采用匹配規(guī)則相似度實(shí)現(xiàn)人工免疫計(jì)算。于海英采用最長公共子序列算法獲取結(jié)構(gòu)相似度，衡量程序代碼相似程度。目前最長公共子串的求解過程可使用動(dòng)態(tài)規(guī)劃（Dynamic Programming）方法。它可在多項(xiàng)式時(shí)間解決兩個(gè)字符串的最長公共子串。鑒于最長公共子串不考慮公共段被隔開多次的問題， 不能很好地表達(dá)一些單詞的相似程度，例如假設(shè) s1為”abcdefg”， s2為”abdes”， s3為”acegt”。直接觀察可以看出，s2比 s3更相似于 s1 ， 但是根據(jù)最長公共字串算法 s1 ，s2 ，s3的最長公共字串長度都為 4，最長子串分別為”abde”及”aceg”。進(jìn)一步觀察可知，”abde” 在 s1 中被分隔為兩段，而”aceg”在 s1 中被分隔為 4 段。經(jīng)典的最長公共子串算法沒有度量這種差異。為了刻畫這種差異并提高對(duì)于單詞相似度的刻畫能力， 本文提出一種改進(jìn)的最長公共字串算法：有限分隔最長公共子串算法。