第4章 数组串与广义表.ppt

* 按照BF算法：当比较到某个位置，不匹配时，不管比过的字符串是什么情况，都要进行回溯！因此，算法效率低。 假设主串为 T=‘t0t1t2...tn-1’ 模式串为 P=‘p0p1p2...pm-1’ mn 基本思想： KMP算法最大的改进之处：在匹配失败时，主串中的指针i不需要回溯，而是在模式中找出适当的字符继续比较。 改进的模式匹配—KMP算法 * 在主串的第i个字符ti与模式中pj匹配失败时，i不回退，而是在模式中找适当字符pk与ti继续比较，pk与ti pk+1与ti+1……..当然此pk不是任意的，得根据一定算法找出。 kj，为什么？ … T i P j k ≠ * t0 t1 t 2 …… ti-k ti-(k-1) ti-(k-2)…. ti-2 ti-1 ti ti+1…… p0 p1 p2…pk-1 pk…. pj-k pj-(k-1) pj-(k-2)…. pj-2 pj-1 pj pj+1 Pj K K K p0p1p2…pk-1 = ti-k ti-k+1 ti-k+2… ti-2 ti-1 pj-k pj-k+1 pj-k+2… pj-2 pj-1 = ti-k ti-k+1 ti-k+2… ti-2 ti-1 p0p1p2…pk-1 = pj-k pj-k+1 pj-k+2… pj-2 pj-1 * 从以上分析可知： p0p1p2…pk-1是 p0p1…pj-1 的既是真前缀、又是真后缀的子串。（即长度小于j）当然，要求这个子串取尽可能长，这个子串越长，说明已经匹配的字符就越多。 所以，求 k 就是求 p0p1…pj-1中最长的既是真前 缀又是真后缀的子串的长度。 k与主串无关！！ * 第1趟 T a b b a b a P a b a 第2趟 T a b b a b a P a b a i=2 j=2 i=1 j=0 第3趟 T a b b a b a P a b a 第4趟 T a b b a b a P a b a i=2 j=0 i=6 j=3 每趟： 主串回溯到上次起点的下一个位置； 模式串回到0 复习： * 运用KMP算法的匹配过程 第1趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c 第2趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c 第3趟 目标 a c a b a a b a a b c a c a a b c 模式 a b a a b c a c 第4趟 目标 a c a b a a b a a b c a c a a b c 模式 (a b) a a b c a c ? * 对于每个pj都求出了最长的既是真前缀又是真后缀的串长度k，那么就有：主串的某个字符与pj匹配失败时，应继续与 pk比较， k称为pj的失败函数值，记作 next[j]=k。 KMP快速匹配算法的实现 * 根据前面的分析，失败函数可以定义为： -1 当 j=0 时 ??? next[j]= max{ k | 0kj且 ‘p0p1...pk-1’=‘pj-k...pj-1’ } 非空 0 其它情况 j k k k 0 pj-k pj-1 失败函数的定义 * 利用next失败函数进行匹配处理 若在进行某一趟匹配比较时在模式 P 的第 j 位失配： 如果 j 0，那么在下一趟比较时模式串 P的起始比较位置是 pnext(j)，目标串 T 的指针不回溯，仍指向上一趟失配的字符； 如果 j = 0，则目标串 T 指针进一，模式串P 指针回到 p0，继续进行下一趟匹配比较。 j 0 1 2 3 4 5