数据结构-C语言描述(第三版)第5章字符串和广义表.ppt

图5－6 KMP模式匹配举例 (a) 主串s和模式串p；(b) 在j=7处失配；(c) 比较从j=f(7)=4处开始 (d) 比较从j=f(4)=1开始；(e) 匹配成功 现在分析Index_KMP算法。该算法中，if (j==－1 || s.chs[i]==p.chs[j])语句的执行次数最多，我们以它的执行次数来计算算法的时间复杂度。 if语句有两个分支： (1) i++; j++; ； (2) j=f[j]; 。 if语句的执行次数是这两个分支执行次数的和。 分支(1)中，i的初值为pos(pos≥0)，因in，因此，分支(1)最多执行n次。分支(2)中，j的初值为0，执行语句j=f[j]后，由于f[j]j，j在分支(2)中只减不增，只在分支(1)中增1，并只当j≥0时，才会执行分支(2)，因此分支(2)的执行次数不会超过分支(1)。所以if语句的执行次数不会超过2n，KMP算法的时间复杂度为O(n)。 3. 计算失败函数 下面讨论失败函数的计算方法。计算f(j)就是对子串p0 p1 … pj－1求最长的且相等的前缀子串和后缀子串的长度。如果这种计算是费时的，则KMP算法不会给我们带来节省时间的好处。幸运的是我们能够设计出快速计算f(j)的算法。 我们知道，总有f(0)=－1。如果已经计算出f(j)(0≤j＜m－1)，如何计算f(j+1)呢? 为了求f(j+1)，根据定义，我们需要求得p0 p1… pj的最长的且相等的前缀子串和后缀子串的长度k，即max{k|0＜k≤j 且 p0 p1… pk－1 = pj－k+1 pj－k+2… pj}。 设f(j)=h，我们有p0 p1… ph－1 = pj-h pj-h+1… pj－1。 　(1) 若ph＝pj，则表明p0 p1… ph = pj－h pj－h+1… pj，并且不可能有hh，使得p0 p1… ph = pj－h pj－h+1… pj，所以，有f(j+1)=h+1。 　 (2) 若ph?pj，则表明p0 p1… ph?pj－h pj－h+1… pj。 设f(h)=g，考察pg 是否与pj相等，如果相等，则意味着p0 p1… pg =pj－gpj－g+1… pj，有f(j+1)=g+1，依此类推。这一过程可看成是主串和模式串都是串p的模式匹配过程。 由此我们可得到计算失败函数f(j)的递推公式： 其中，f1(j)=f(j), fm(j)=f(fm－1(j))。 根据上述分析，我们得到程序5－4的计算失败函数值的C程序。 【程序5－4】 失败函数的C程序。 void Fail(String p, int *f) { int j=0, k=-1; f[0]=－1; while (j p.Length) if (k==-1 || p.chs[j]==p.chs[k]){ j++; k++; f[j]=k; } else k=f[k]; } 4. 改进的失败函数的C程序 失败函数可以通过改进，进一步提高效率。从图5－6可以看出，在第1趟匹配到达失配点时，s7=a，p7=b，s7≠p7，取j=f(j)=4，即下一趟从p4开始与s7继续比较。由于p4=p7=b，因此p4≠s7，此趟回溯到j=4仍然是多余的；同理回溯到j=1也是多余的，可以直接回溯到j=0。这就是说，如果在求得f(j)为k值后，若有pk?pj，可令f(j)=k，否则令 f(j)=f(k)。改进的失败函数的例子见表5－2。改进的失败函数的C程序见程序5－5。 表5－2 改进的失败函数的例子 j 0 1 2 3 4 5 6 7 8 9 10 P a b c a b c a b b a c f(j) －1 0 0 －1 0 0 －1 0 5 －1 1 【程序5－5】 改进的失败函数的C程序。 void Fail2(String p, int *f) { int j=0, k=－1; f[0]=－1; while (jp.Length) if (k==－1 || p.chs[j]==p.chs[k]){ j++; k++; if (p.chs[j]==p.chs[k]) f[j]=f[k]; else f[j]=k; } else k=f[k];