数据结构-北大计算机系讲义

1、(1)KMP算法T t0 t1 tj-i-1 tj-itj-i+1tj-i+2tj-2tj-1tj tn-1 P则有p0p1p2pi-2pi -1pitj-i tj-i+1 tj-i+2 tj-1 = p0 p1p2 pi-1(1)为使模式 P 与目标 T 匹配，必须满足p0 p1p2 pi-1 pm-1= ts p1ts+1 ts+3 ts+i ts+m-1p0 p1pi-2p2 pi-1(2)则立刻可以断定p0 p1pi-2 tj-i+1 tj-i+2 tj-1)下一趟一定不匹配，可以跳过去计算机系1 p2p0 p1pi-3p3 pi-1同样，若则再下一趟也不匹配，因为有pi-3 tj-i

2、+2 tj-i+3 tj-1p0 p1直到对于某一个“k”值(首尾串长度)，使得 pi-k-1 pi-k pi-1p0 p1 pk且则p0 p1pk-1 = pi-k pi-k+1 pi-1p0 p1pk-1 = tj-ktj-k+1tj-1tjpipi-kp0pi-k+1p1pi-1pk-1模式右滑i-k位计算机系pk2模式右滑i-k位tj-ip0tj-i+1p1tj-i+2p2tj-kpi-kp0tj-k+1tj-1pi-1pk-1tjpipkpi-k+1p1计算机系3next数组值序号iPk pk=pi? nexti0a1b 002c 03a04a15b 16a 27b 18c 2 =

3、= = =-10-110200计算机系4运用KMP算法的匹配过程第1趟 目标模式a a b c b a b c a a b c a a b a b c序号i01b02c03456a27b08c0a b c a a b a b cPa-1aa-11b0next(1) = 0nexti第2趟 目标模式a a b c b a b c a a b c a a b a b c a b c a a b a b c next(3)= -1a a b c b a b c a a b c a a b a b c a b c a a b a b c第3趟 目标模式(j+)(i=0)next(6) = 2第4趟 目

4、标模式a a b c b a b c a a b c a a b a b c(a b) c a a b a b c计算机系5KMP算法void KMPFind(const Stringi=0, j=0, len_t, len_p, *next;, const String pat,& index) len_t =next.Length();len_t;len_p = pength();Get_NextArr(pat, next);j = pati) / compnext pair of charsompares withjp)en_p;/ sucs, return start poe inde

5、x/ failure, return -1;计算机系6(2) next数组性质a)匹配失败，pitj时，j永不回溯希望找到pk(ki)与tj比tj-i p0tj-k pi-k p0pi-1tj-1tj pi pkpi-1pk-1= p0如果pi-k则p0pk-1，pk-1不用比pk(ki)与tj可以直接比较计算机系7最大首尾子串b) 为了保证p的右移不丢失信息(滑动i-k=i位，如果有更大的k值，但取了小k值，则滑动过大，可能丢失潜在的匹配位置)，取p0pi-1的最大首尾子串长度k为nexti值next0 = -1;nexti=maxk | 0=ki,p0pk-1=pi-kpi-1注：i)若k

6、=0，即不存在这样的真子串只能用p0与tj比(滑动i-k=i位，滑动幅度最大，效果最好)tj-i p0tj-1 pi-1tj pi p0计算机系8ii)若k=i-1, 真子串最长(滑动最小)p0pi-2=p1pi-1tj-i p0tj-i+1 p1 p0tj-1 pi-1 pi-2tj pi pi-1iii)i=0, 第就第一不个个等就，不再等等无，再无可k与不i可等与，可tj 与比nexti=-1，j+;i=0;计算机系9c)next数组的改善i)若pk=pi， pitj pktj本来应该拿Pnexti（即pk ）与tj比此时应该用Pnextnexti比，计算机系10(3)求next数组步骤

7、a) next0 = -1; next1 = 0;if (p1=p0)next1 = next0;i=1;k=0;计算机系11b)假设next0.i都已求出，要求nexti+1且p0pi-1的最大首尾子串长k(k=0，且pkpi时反复执行：/ 此时又是一个模式匹配问题T=P/ 应该用Pnextk来匹配pi，/ 若Pi=Pnextk，说明串p中第i+1个字/符前存在一个长为k+1的最长子串k=nextk;计算机系12ii) i+;k+;/ i=i+1, k=k+1 / 最长子串为k+1, nexti+1 = k+1/ 当Pi+1发生不匹配时，应该拿Pk+1比/ 而pk+1=pi+1，实际就是拿P

8、nextk+1比iii) 若pk = pi则 n则exti = nextk (ki)否否则否则nex则ti = k;计算机系13求Next数组的函数void Get_NextArr(const String pat,i, k, len;next) len =ength();next0 = -1;next1 = 0;if (pat0 = pat1)1; k = 0;next1 = next0;while (i= 0 & patk k = nextk;k+;i+;if (patk =nextk;= k;计算机系143.next数组举例序号iPk pk=pi? nexti0a1b 002c 03a04a15b 16a 27b 18c 2 = = = =-10-110200计算机系15KMP算法性能分析目标串的检测指针每趟不回退，因此j+和i+最多执行n次（更准确的说法是n-m次） i的初始值为0，除中间有“next(i)=1;”的值使得i的值变成-1，但马上会调整为“j+; i=0;”外，算法结束时i一定大于0。循环体中“i=next(i);”语句的执行次数过