同样,若pP1…P3≠P2P3…1 再下一趟也不匹配,因为有 到对 值(首尾串长度),使得 模式右滑广位 乐5升+152…5k5k+1…515 P0p1…Pk≠PHk1P… 且 PP1…Pk-1=phkP+1…P1 PkPk1…1P 模式右滑j位PPM+1…PP Po pI 辆则/:=5k541…51m|辆 与≠,P==pk 北京大息 孔帖检写 342字符串的特征向量N 特征n的含义 设模板P由m个字符组成 aP的首子串qq1q2qt-1 记为P=qoq1q2q32…qm1 P的尾子串q+q12q1q1 ■特征向量N用于表示模板P的字符分 布特征 特征数n1 no n1n2n3…nm-1 最长的(t最大的)首尾子串能 m个非负整数 够匹配的t 大带_息 张写 积新有,神 张所有,赖 N=[23|o山23d 特征数n的递归定义 ①n=0, P=aalaabla aa 对于i>=1的n1,假定已知前一位置 的特征数n1,并且n1=k 前缀→ ②如果q=qk,则n=k+1; 前缀 ③当q≠q且k≠0时, 前缀→ 求特征向量N 则令k=n 前缀→ 让③循环直到条件不满足 ④当q≠q且k=0时,则n1=0 北底大 张储帖写 真大带健意张写c所有,邮必究 e 66 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 back next 同样，若 p0 p1 …pj-3 ≠ p2 p3 …pj-1 则再下一趟也不匹配，因为有 p0 p1 …pj-3 ≠ si-j+2 si-j+3 … si-1 直到对于某一个“k”值(首尾串长度)，使得 p0 p1 …pk ≠ pj-k-1 pj-k …pj-1 且 p0 p1 …pk-1 = pj-k pj-k+1 …pj-1 si-k si-k+1 … si-1 si ‖‖ ‖ pj-k pj-k+1 … pj-1 pj ‖‖ ‖ p0 p1 … pk-1 pk 模式右滑j-k位 × ? 则 p0 p1 …pk-1 = si-k si-k+1 … si-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 back next 模式右滑j-k位 si-j si-j+1 si-j+2 … si-k si-k+1 … si-1 si ‖ ‖‖ ‖ ‖ ‖ ‖ p0 p1 p2 … pj-k pj-k+1 … pj-1 pj ‖‖ ‖ p0 p1 … pk-1 pk × ? p0 p1 …pk-1 = si-k si-k+1 … si-1 si ≠ pj , pj ==pk? 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 back next 3.4.2 字符串的特征向量N „ 设模板P由m个字符组成： 记为P = q0 q1q2q3……qm-1 „ 特征向量N用于表示模板P的字符分 布特征 „ N ＝ n0 n1n2n3……nm-1 „ m个非负整数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 back next 特征ni 的含义 „ P的首子串q0q1q2…qt-1 „ P的尾子串qi-t+1...qi-2qi-1qi „ 特征数ni „最长的（t最大的）首尾子串能 够匹配的t 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 back next 特征数ni 的递归定义 „ ① n0＝0， 对于i >= 1的ni ，假定已知前一位置 的特征数ni-1 ，并且ni-1＝ k ； „ ② 如果qi ＝ qk ，则ni ＝ k＋1 ； „ ③ 当qi ≠ qk 且 k≠0时， 则令k ＝ n k -1 ; 让③循环直到条件不满足； „ ④当qi ≠ qk 且 k ＝ 0时，则 ni ＝ 0; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 back next 求特征向量N N = 2 3 0 1 2 P = a a a b a a a 0 12 3 4 5 6 a a c 789 3 4 0 前缀→ a 前缀→ a a 前缀→ a a a 0 1 前缀→ a 前缀→ a a 前缀→ a a a 前缀→ a a a a