第六章字符串处理算法.ppt

-:字符串精确匹配(ExactStringMatching)问题可以描述如下:给定一个长字符串T和一个短字符串P,其中它们的长度分别是|T|=m,|P|=n,利用最理想的时间和空间找出全部的T中与P完全匹配的子串****惯的表示方法:字符串T/P中的第i个字符用T(i)来表示。-box算法[定义]Zi(S)表示在字符串S中从第i位起与S的前缀匹配的最长的字符串的长度。(数值)注:如果S在上下文中很明显,Zi(S)可以用Zi来表示。例:S=aabcaabxaaz那么12345678Z5(S)=3;Z6=1;Z7=Z8=0Z-box:其中每个与前缀匹配的子串就叫一个Z-box。对于任意数字i,如果S(i)属于某一个Z-box,则定义Li表示该Z-box的最左端的位置,Ri表示该Z-box的最右端的位置。例:在上例中L6=5R6=7性质:ifi>j,thenRi>=Rj[任务]在线性时间内(O|S|)计算S的所有Zi[思想]Z2正常计算,然后归纳计算Zk,可以减少比较的次数[思想]令S=P$T,其中$是特殊字符,在S和T中都不存在。利用Z算法计算Zi(S)。[方案]对于任意j,如果Zn+1+j(S)=n,则P出现在T(j)处。[加强]因为$的设定,对于任意i都有Zi<n,即k`总落在P内,所以当k>n时(即在T中)Zk值不用计算,只需要维持(maintain)R和L的值。[名称]Boyer-Moore算法[特点]从左向右移动,自右向左扫描[技巧]坏字符规则 [实质]把P中的坏字符x移到T中的x的下面[定义]对于字母表中的每一个字符x,R(x)表示x在P中的最右端的位置,如果P中没有x,则R(x)=0。[规则]对于P和T,如果P右面的n-i个字符都和T匹配,但是P(i)≠T(k)。那么P可以向右移动max[1,i-R(T(k)]位。