【题04】计算最长重复子串--试题解析.doc

《【题04】计算最长重复子串--试题解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途串运算的应用——子串模式匹配设s为主串，t为模式串，ｑ为ｓ中第一个与t相等的子串。所谓模式匹配指的是⑴若q存在，则计算出q的首字符在s中的位置；⑵若q不存在,则返回０。模式匹配的算法有很多。为便于讨论，以后我们将主串ｓ的长度设为n，匹配指针为k；模式串ｔ的长度设为m。朴素的串匹配算法:1.ｆoｒk←1ton-m+１　do　ifcｏpｙ(t，1,ｍ)＝copｙ(s，k,m)then输出k;如果以字符匹配为计算单位的话,这种算法最坏情况下的运行时间为O(　(ｎ-m＋1)m)。问题是，有没有时效更高的匹配算法?有的,kmp算法就是其中最出色的一个算法

2、。我们从一个实例引出讨论【题４】计算最长重复子串在一个字串中,多次出现的子串称为重复子串。如果这样的子串有多个，则其中长度最长的子串称为最长重复子串。例如ｓ＝'abcdacdaｃ＇，则ｔ=＇cdaｃ＇为ｓ的最长重复子串。请你在尽可能短的时间内找出最长重复子串。输入:字符串s,长度不超过２5５输出:s的最长重复子串分析：1、ｋmｐ算法朴素的串匹配算法的时效之所以不尽人意,是因为有重复的计算。看下面的例子：模式ｔ=‘ATATＡCＧ’的第６个字符在当前位置无法匹配，朴素的串匹配算法将ｋ递增1，从t的第一个字符开始重新匹配,但实际上此时可将k递增2，从t的第4个字符开始匹配，

3、因为在这之间的匹配肯定会失败。类似的例子随着数据量的增大而越来越多，朴素的串匹配算法将做更多的重复工作，使得时效很低。为什么可以让k递增２，从t的第4个字符开始匹配呢?这是由t的性质决定的。　　如上图所示，ｔ的前缀‘ATA’恰好是ｔ的前缀‘ATATＡ’的后缀,所以如果直到‘ATＡＴA’都匹配成功,而‘ATATAC’匹配失败,则主串s的子串sk+2‥ｓk＋4必定为‘ＡTA’(因为‘ATAＴA’在k处匹配成功，sk‥ｋ＋4＝‘ＡTATA’)，于是t的前缀‘ＡTA’肯定在k+2处匹配成功。KMP算法正是利用了这种特性使得算法的时间复杂度降为O（n+m)。算法的关键是求t的前

4、缀函数next,使得ｎext［j]　=max{k

5、ｋ

6、ext[５]＋1＝=４；t[６]前的任何一个前缀都不含字符‘C’,得出next［7］=1。显然,在s与t顺序匹配的过程中,如果t[j]与主串s的当前字符不匹配,则s的当前字符与t[nｅｘｔ[ｊ］]比较，不需要从t[1]开始重新比较。移动的位置与s无关,取决于模式串t本身,求ｎeｘｔ(j）实际上就相当于用t匹配ｔ的过程。由于这个匹配过程是按照字符顺序依次进行的，因此是一个递推过程。设Tｙpｅnexttype=arｒay[１.．25５]ofｉｎteｇer；Ｖar　ｎeｘt：nｅxttyｐe；　　　　　　　　　　　　　{ｔ的前缀函数}我们通过geｔ_ｎｅxt过程计算模式串t

7、中每个字符的neｘt值ｐｒoｃedure　get＿nｅxｔ(t:string；ｖａrnext:nextｔype);　　varｊ,k:intｅger;begiｎj←1；k←０;next[1］←０;　　　　　　　　　　　　　{初始化}　　whiｌe　ｊ<=leｎgtｈ(ｔ)do　　　　　　　　　　　　{循环，求每一个字符的ｎeｘt值}　if(k＝０)or（t［j］＝t[k］）thenbegｉｎ　　　　{若不存在可匹配的子串或比较相等，则ｎeｘt［j+1]←neｘt[j]+1}　　ｊ←j+1;　k←k+1；ｎeｘt［j]←ｋ;　　　　　　ｅnd　｛ｔhen}　　　elｓe　

8、ｋ←next[k];　　　{否则依次类推找更短的子串}enｄ;　{ｇet_next}显然，如果模式串ｔ的串长为m,则gｅt_ｎext过程的时间复杂度为W（m）。２、使用ｋｍｐ算法寻找子串我们定义indｅx（ｓ,t)为求模式串t在主串s中位置的函数。让模式串t自左至右在主串ｓ上滑动进行匹配检查。设q为s中第一个与ｔ相等的子串，若q存在,则函数iｎdeｘ(s，t)的值为ｑ的首字符在ｓ中的位置，否则函数值为零。(t不能是空串)。　例如:a＝'ｂei';b='beiｇｉng';ｃ=＇i'；个人收集整理勿做商业用途　则　indｅx(b,a）=1；　　　　ind