第4章串.ppt

讨论一般情况。 主串S为 ‘s1s2 … si -1si …sn’， 模式串T为‘p1p2… pj -1pj … pm’ 当si !=pj时， si应与T中哪个字符再比较？ 假设应与pk继续比较，则模式中前k – 1 个字符的子串必须满足下列关系式 ‘p1p2…pk-1 ’= ‘si-k+1si-k+2……si-1 ’ (4-2) 而已经得到的“部分匹配”的结果是 ‘pj-k+1pj-k+2……pj-1 ’= ‘si-k+1si-k+2……si-1 ’ (4-3) 由（4-2）和（4-3）推得下列等式 ‘p1p2…pk-1 ’ = ‘pj-k+1pj-k+2……pj-1 ’ (4-4) 匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。 设next[j] = k，由此可引出模式串的next函数的定义： 0 当j = 1 时 next[j] = Max {k | 1 k j 且‘P1…Pk-1’= ‘Pj-k+1…Pj-1’} 当此集合不空时 1 其它情况 由此定义可推出下列模式串的next函数值： j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2 int Index_KMP (SString S, SString T, int pos ) { i = pos ; j = 1 ; while ( i = S [ 0 ] j = T[ 0 ] ) { if ( j = = 0 || S[ i ] = = T[ j ] ) { ++ i ; ++ j ; } // 继续比较后续字符 else j = next [ j ] ; // 模式串向右移动 } if ( j T[ 0 ] ) return i – T [ 0 ] ; // 匹配成功 else return 0 ; } // Index_KMP 怎么求next数组的值？用递推的方法：归纳法 设next(1) = 0，设next(j) = k，欲求得next[j+1]。 （1）如果Pk = Pj，显然next[j+1] = k+1。 （2）如果Pk ≠ Pj，则 ‘p1p2…pk ’ ≠ ‘pj-k+1pj-k+2……pj ’ ，这就可以看成是一个模式匹配问题，主串和模式串是同一个串。于是寻找k’, 若next[k]=k’，使得‘p1p2…pk’’ =‘pj-k’+1pj-k’+2……pj ’ ，则next[j+1]=next[k]+1。如果等式不成立，则继续找下一个k’，这是个迭代的过程。 （3）如果不存这样的k’,说明P0 P1……Pj中没有前后相等的子串，因此next[j+1] =1。 仿照KMP算法，可得到求next函数值的算法。 void get_next ( SString T , int next[] ) { // 求模式串T的next函数值并存入数组next。 i = 1 ; next [ 1 ] = 0 ; j = 0 ; while ( i T [ 0 ] ) { if ( j = = 0 || T [ i ] = = T[j] ) { ++ i ; ++ j ; next[i] = j ; } else j = next[j] ; }//while } // get_next 说明： 1）算法4.5在一般情况下，其实际的执行时间近似于O(n+m)，至今仍被采用。 2）KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比算法4.5快的多。 3）KMP算法的最大特点是指示主串的指针不需回溯，对主串仅需