串的最大匹配算法页码：　１／４

串的最大匹配算法　

林毓材　张建军　向永红　张春霞　

（云南师范大学计算机科学系，昆明，６５００９２）　

摘要：给定两个串Ｓ和Ｔ，长分别ｍ和ｎ，本文给出了一个找出二串间最大匹配的算法。该算法可用于比较两个串Ｓ和Ｔ的相似程度，它与串的模式匹配有别。　　

关键词：模式匹配　串的最大匹配　算法　

Algorithm on Maximal Matching of Strings

Lin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun （Computer Science Department of Yunnan Normal University Kunming 650092）

ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T, it is different with the strings' pattren matching.

KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm 　　

１　问题的提出　　

字符串的模式匹配主要用于文本处理，例如文本编辑。文本数据的存储（文本压缩）和数据检索系统。所谓字符串的模式匹配［２］，就是给定两个字符串Ｓ和Ｔ，长度分别为ｍ和ｎ，找出Ｔ中出现的一个或多个或所有的Ｓ，在这方面已经取得了不少进展［３］［４］［５］［６］［７］［８］［９］［１０］［１１］。本文从文本处理的另一个角度出发，找出两个串的最大匹配，比较其相似程度［１］。它主要应用于文本比较，特别是在计算机辅助教学中。显然前者要找Ｓ的完全匹配，而后者并无此要求。例如，若Ｓ＝ＡＢＣＤ，Ｔ＝ＥＦＡＢＣＤＸ，那么模式匹配的结果就是找出了Ｔ中的一个ＡＢＣＤ，而我们算法的结果就是Ｓ能与Ｔ的ＡＢＣＤ完全匹配，但是Ｔ中还有３个字符是比Ｓ多出来的，也就是说在Ｓ中有１００％的字符与Ｔ中的匹配，而在Ｔ中有５７％的字符与Ｓ中的匹配。若Ｓ＝　

ＡＢＣＤＦＥ，Ｔ＝ＡＦＸＢＥＣＤＹ。则在模式匹配中Ｓ与Ｔ无匹配项，但在我们的算法中就能发现Ｔ中存在Ａ，Ｂ，Ｃ，Ｄ，但Ｄ后不存在Ｅ，Ｆ。而且Ｓ中也存在Ａ，Ｂ，Ｃ，Ｄ，且具有顺序性。这样就能公正地评价Ｓ，Ｔ的区别。得知其相似程度。　　

文章的组织如下：首先介绍基本定义和问题的描述；第三节是算法设计；最后是本文总结。　　２　问题的描述　　

设∑为任意有限集，其元称为字符，ｗ：∑→Ｎ为∑到Ｎ的函数，称为∑的权函数（注：本文仅讨论权值恒为１的情况）。∑＊为∑上的有限字符串集合，那么对任意Ｓ，Ｔ∈∑＊，设Ｓ＝ａ１ａ２…ａｍ，Ｔ＝ｂ１ｂ２…ｂｎ，ｍ＞０，ｎ＞０。记＜ｍ＞＝｛１，２，　…，ｍ｝，＜ｎ＞＝｛１，２，　…，ｎ｝，则称｛（ｉ，ｊ）∣ｉ∈＜ｍ＞，ｊ∈＜ｎ＞，ａｉ＝ｂｊ｝为Ｓ与Ｔ的匹配关系集，记作Ｍ（Ｓ，Ｔ），称Ｍ为Ｓ与Ｔ的一个（容许）匹配，若对任意（ｉ，ｊ），　（　ｉ＇，ｊ＇　）∈，①　ｉ＜　ｉ＇，当且仅当ｊ＜　ｊ＇，②　ｉ＝　ｉ＇当且仅当ｊ＝　ｊ＇。Ｓ与Ｔ的匹配中满足

阵，且满足：　　最大者，称为Ｓ与Ｔ的最大匹配。若Ｃ（ｉ，ｊ）为Ｎ上的ｍ×ｎ矩

则称矩阵Ｃ为串Ｓ与Ｔ的匹配关系阵。　

于是求串Ｓ与Ｔ的最大匹配，等价于求Ｃ中的一个最大独立点集Ｍ，它满足，若ｃｉ，ｊ，ｃｉ＇，ｊ＇∈Ｍ，则ｉ＜　ｉ＇　当且仅当ｊ＜　ｊ＇，ｉ＝ｉ＇当且仅当ｊ＝ｊ＇。我们称这样的最大独立点集为Ｃ的最大Ｃ－独立点集。　

例：设∑为所有字母的集合，对任意ｘ∈∑，ｗ（ｘ）≡１，设Ｓ与Ｔ分别为：Ｓ＝

“ＢＯＯＫＮＥＷＳ”，Ｔ＝“ＮＥＷＢＯＯＫＳ”。则我们可以得到Ｓ与Ｔ两个匹配：