信息学-集训队作业

市外国语学校[关键字]模式串单词前缀树后缀树[KMP法以及后缀树算法另外基于KMP算法的思想在第四章足于线性时间复杂度，接着在第六章提出了平均性能更好的算升到理论高度。 Knuth-Morris-Pratt 模式串的前缀函数（Prefix kmp 单词查找树（Trie） §4主算法一（线性算法 kmp McCreight 建立后缀树（初步 后缀 §6主算法二（平均性能更好的算法 TreeATreeB §1§1.1所谓多串匹配，就是给定一些模式串，在一段文章（az26）中，找出第一个出现的任意一个模式串的位置。具体来说就是：mL1、L2……LmP1[1..L1]、P2[1..L2]……Pm[1..LmnT[1..n]，L100K,m1000,n900K 要找到一个最小的整数s[1,n]，满a[1m]

注：如模式串为cdefg与efg，正文为abcdefgh时，会造成匹配目标的不（§1.2ForFori1tonForj1tomDo 该算法从小到大枚举每一个位置，并且进行检查情况下时间复杂度。O(nL)。 i1to XiPiT O(nLi内完成。因此总复杂度为O(nmL)，可惜这两种方法面对即将解决的数据量，是力不从心的应该努力想出一种线性,或者更优秀的算法。为此，要先介绍一个预备算法——，（Knuth-Morris-Pratt）§2Knuth-Morris-Pratt特————特操作，简称kmp算法。§2.1到所有的整数

对于x[1m]都有T[sx-1P[x§2.2模式串的前缀函数（Prefix对1im有前缀函数π(imaxj|P[1..jP[i-j1..i0Fori2tom k>0and End因为k的增加值最多为m-1（最多进行m-1“kk+1”）,所以“kπ[k]”m-1该程序段的复杂度为O(m)。§2.3kmp图如图2，当在串中匹配到了“”的时候，可以根据π[5]=3，将模式串5-3=2（π进行右移……。类似于计算前缀数组的方法，也不难写出这段主算法的伪代码Fori1ton q>0and writei-mEndIfEndFor与计算前缀函数的算法相同，qπ[q]的执行次数不会超过n次。因此，整kmp算法的时间复杂度为O(nm)§3§3.1单词查找树（Trie）词树是一棵无限延伸的26叉树。每个结点的26个通向子结点的边，被分别命名a,b……z。对于每一个结点p，从根结点至p的路径上的所有字母，可以连成一个字符串，定义这个字符串为Sp。反之，对于一个字符串S，根据该字符串上§3.2当然实际情况下不能让这棵单词查找树无限延伸因此在一棵初始3：aNILaNIL……zaNIL……bzaNIL……bzaNIL……zaaNIL……bzaNIL……b aNIL……zaNIL……bzaNIL……zp=Fori1tonp=Fori1ton NEWp->Child[S[i]];并对其初始pp-Endp->Child[ch](ch[a..zpch§3.3缀指针（PrefixPointerp找到最小的整数k[2,|Sp|，使得Sp[k..|Sp| b ab ppS b ab 考虑阴影结点p。Sp=abab。先找bab，不过这个字符串没有在单词树中出现，因此再找ab，这一次找到了。§3.4杂度是可想而知的。仿照kmp算法中的前缀函数，不难想到，可以通过父结定义一个结点的前缀指针所指向的结点为该结点的前缀结点p q<>Rootandq->Child[ch]= qq- q->Child[ch]= p- p->Prefixq-5结点结点 结点 b结点aappq1，q1bq1§4主算法一（线性算法§4.1kmpkmp移量当然很想效仿这个算法对文章进行仅一次扫描那么就需要当6： a abababaca2个无奈的，也是很好的选择。再加上kmp的前缀函数的启发，就设计出了§3§4.2缀树的基本元素根据§3提到的单词前缀树的建立方法可以把所有模串一棵空的树，并且计算好它们的前缀。Paaa

处建立一个附加标记（后面称此标记为Okay标记Okay=aabcdbc7： bccqdp全。这个过程怎么弥补呢？不难发现q结点是p结点的前缀结点。因此想到OkayOkayOkay标记。§4.3nP[1..n]piP[1..i]在单词树中对应的结点那么证明p0(Root),p1……pn的前缀指针计算复杂度之和为O(n)。证设ci(0inpi结点的前缀指针的代价（c01。势能函数将结点pi为一个实数Φ(i)(0in)，即结点pi的势，在此定义Φ(0)0chq->p q<>Rootandq->Child[ch]= qq- q->Child[ch]=chq->p q<>Rootandq->Child[ch]= qq- q->Child[ch]= p- p->Prefixq-多为Φ(i1Φ(i1pi+1的前缀指针的代价ci1=1+“Φ(i2Φ(i1。对所有0in，将ci1nnci2nΦ(0)Φ(n)nO(n由此不难得出，整个单词前缀树的构造时间复杂度为O(L)§4.4仿照kmp算法的主过程，的多串匹配算法也可以大功告成了AlgorithmAlgorithmMulti-PatternMaching1;预处理建立单词前缀树Fori1ton q≠Rootandq->Child[T[i]]= -EndFor注意，与kmp主算法相同，->Prefix的次数不会超过->Child[T[i]]的总次数，因此这一段程序的时间复杂度为O(n。babaazababaabcaba§4.5总时间复杂度为这两部分的时间复杂度之和，为O(Ln所以在单词树中需要使用O(26L间，因此整个程序的空间复杂度为O(26L)§4.69a 01a01100001a01a01100001通过二分查找。这样一来程序的时间复杂度将略有下降，但空间复杂度降为O(L)§5McCreight§5.1面已经介绍过了。对于单词“ababc10： bc

一共5个叶结点，分别代表了5个不同后缀（称后缀对应的结点为“终结点O(N2)级别（N为单词的长度，那么其势必会影响程序的运行效率。改进的思想是进行路径的压缩，如11： c c 26个子结点，并且通向子结点的边上O(N)级别。致在某条边的中间出现了一个“终结点！这是很麻烦的，因此在原字符串如“$，来避免该情况的出现。§5.2S[1..n]，sufi=S[i..n]Si长的后缀。TpointTpointp提到p:Tpoint->String[‘a’..’z’,’$’]p§5.3建立后缀树（初步McCreight算法用n步建立后缀树T，T初始为空，第i步将sufiT。定义headi为sufi和sufj（1≤j＜i）的最长公共前缀中最长的。并定义sufi=headi+tailiForFori1tonNEWp->Child[taili[1]];p->String[taili[1]]EndS=“abab$ $ $ab$ 显然，taili的时间复杂度仅为O(1)，因此找到headi对应的结点位置，§5.4后缀性质1headi-1可以写成xx是一个可能为空的字符串，那么headi的前缀。j（j<i-1，满足xsufj的前缀，那么sufj+1的前缀。又因为sufi的前缀，因此headi的前缀。后缀的定义p，其对应的字符串可以写成xx是一个字符，是一个可能为空的字符串。定义：p结点的后缀指针p->Suffix指向在树中的位置（如果为空串，则指向根结点。定义根结点的后缀指向自 c c后缀的建立建立过程中使其满足性质2：每一个非叶结点在被创建后，其后缀立即被计算。1，不难得：后缀开始，向下检索：ProcedureProcedureCount_Suffix_Link(p:Tpoint) p->Father到p q= s≠‘’ L=|s|and NEWr:Tpoint; ExitEnd EndWhileEnd3，(*)ss1的最长公§5.5headiheadi-1对应结点的前缀指针开始，向下检索ForFori1tonNEWq->Child[taili[1]];q->String[taili[1]] End时间复杂度分析1、3、4O(1)O(N)语句5，即所有非叶结点后缀的计算，因为Count_Suffix_Link的(*)处O(N)。2O(|headi|-|headi-1|+1)O(N)。McCreightO(N)。§6主算法二（平均性能更好的算法§6.1 为了适用主算法二，还需要在每一个结点增设一个参数Shift。它记录每一也可以通过前缀指针，其中树中的边的权值为1，前缀指针的权值为0。这个Shift参数代表如果指针指向该结点，那么至少需要读入多少字符，才有可能得ababbabb2 a1b OkayShiftShift参数的建立是很容易想到的，模式串Pi的第j个字符时，设newLij(1

jLi

(1Li如果建立了一个新结点p，那么p->Shift 如果达到了一个已经存在的结点p，那么p->Shift min{p-仅仅这样当然是不够的，因为还没有考虑前缀。注意到前缀总是从下层指向上层因此进行一次按照层号从小到大的遍历并且对每个结点p：p->Shift min{p->Shift,p->Prefix->Shift}§6.2ababbabbbabaabbb15所示：aabb 注：与§5所述不同，在图中，没有出现含“$”的边。这是因为根据$§6.3TreeATreeBFunctionFunctionTreeApointT[L..R]，point point- 最短的模式串的长度div TreeA中，pointEndwrite过程所有遇到的所有Okay（遇到的所有匹配returnpointEnd2FunctionFunctionL。End这个过程如果返回了L，说明T[L..R]是某一个模式串的子串，否则不是。当T[L..R]是某个模式串的子串时 称其“有效的反之称其“无效的§6.4AlgorithmAlgorithmMulti-PatternMachingTreeAL0; R最短的模式串的长度;pointTreeA.rootWhileR<=nposScanB(L+1, pointTreeA.root;(L,point)ScanA(pos,R,point);RL+point->ShiftEndWhileEnd在R之后。从R开始反向检索（ScanB，设ScanB在pos处停止：如果pos=L+1，那么T[L+1..R]为“有效的因此可以正向（ScanA）L+1继续往后检索。pos>L+1T[L+1..pos-1]的每一个字符，均不可能成为某个匹配的模式串的串头（L+1<=x<=pos-1T[x..R]必为“有效的，而ScanB的检索终止在pos处，T[pos..R]是“有效的因此可以将point重置为TreeA的根结点，并pos往后检索（ScanA。ScanA，ScanApoint->Shift>=div2”R-L>=最短的模式串的长度div2。图16可以清楚地主算法二的工作顺序 ScanA§6.5abbccddeabbccdde图图其中每个结点上的数字代表矩形为Okay结点他们的Shift参数如下123456789432113214T=“abcabcde阶段1：L=0,R=4,capos=4pos>L+11..3的正文位置上，不可能出现模式的匹配，18： caTreeA上，从point=1开始，走过字符[pos..R]=“apoint=2。因为Shift[2]=3>=最短的模式长度div2ScanApoint=2处停止。阶段2：L=4,RL+Shift[point7,RL逆向进行ScanBbcd”为“有效的ScanBpos=5处停止，pos=L+1，因此不用修改point值，直接正T[pos..R]进行ScanA扫描，pointabcdScanA继续扫描字符“epoint589，又发现一个匹配。§6.6单词前缀树和后缀树的建立时间复杂度为O(26L（，，θ2当所有的模式串长度均为θ，且θ足够大时，若正文随机，并且字母表足够O(N)，下面将完成平均复杂度的计算和证明：θ，设

Lθkθk个较小的常数。设为字母表（alphabet）的大小（26或者其它θ和够大，可令其满足log

M3θ即3k

θ2ScanBScanA的循环为一个阶段命题 每一个阶段中，R-L的数量级为O()Shift≥θdiv2R≥L+θdiv2R-L的数量级为O()。命题2 一共有最多O(n/)的阶段。由命题1，这是显然的。命题3 有不超过2k个“有效的”字符串命题 存在一个常数C，使得每读入Clog个字符，其组成的字符串

1PM证明由命题3，有不超过2k个“有效的”字符串。而长度为Clog字符串有

读入一个“有效的”字符串

1

C3k常数。根据条件有Clog2命题5ScanATreeAxp时，若对应正文字T[y]T[y-x+1..y]必为“有效的证明T[y-x+1..y]TreeA.Rootp结命题 ScanA中，读到Shift≥2

的结点并结束扫描，需要在[L..R]多读入字符数的期望值为O(log)证明若在读入前Clog个字符中，ScanAO(log。若在读入Clog~2Clog的字符中，ScanAClogTreeApoint的深度必然大于等于（若小于 point->Shift，而Clog

5可得这Clog 的字符串是“有效的41MxClog~(x+1)Clog的字符中，ScanA。M 因此期望值小于(x1)Clog

O(log)命题7 每一个阶段读入字符数量的期望值为O(log)。证明分两种情况1、ScanB读入的字符数小于等于Clog41M

。ScanA将从TreeA的根结点开始，读入最多ClogClog2

参数必然大于等于2

Clog2、ScanB读完第Clog41ScanB的ScanA的MScanAShift参数不满足而附加读入的Clog个字符（6

1)2ClogM

1(2Clog)O(log)结论由命题2和命题7可得本算法的平均复杂度为O(nlog§7§7.1主算法二中使用了2

ScanA退出的标志。R-L的长度下限。2如果2

变大，那么ScanA的退出将变得更因 是一个恰好使得平均复杂度取得最小值的中间点2§7.2多种算法并用（比如本题的单词前缀树和后缀树）优劣得