2014/47 §4.3模式匹配算法 $4.3模式匹配算法 ④若P1.于-川不存在首尾相同的字符串，或者说仅存在长度为零的 ■next数组生成（递推法） 相同前后绿（空串）子串，则k一1，即p,与继续比较 特别地，若（即抑），则P中任何字符无法与缝蝶比较，P 设next=j已知，求nexti+1小e1) 右移1位，将p和t继续比较。按next定义，可取next1-0(对 由性质4告知我们，对任何模式P,总有mext1=0 任何P成立)。 成立，给出了递推基础 综上所述，当邦时 ,next[1]-next[已知，且已知next i=j 0 .P1i1中有： nxt-P1.…小l中前后佩相等的量大离子事的长度加1（包括空率），即： “p…p.”=“p1P”最大真子串长度为j-门 am因sy且”p4p"-一pk…p=I时为空审 扩充一个字符p后，比较pp 例， ①若pp,则P1.jP时1. j|12345678 即P1.中前后缀的最大真子串长度为j,故 Pa b aa b c a c next i+-1-j+1或者next i+1=next i+1 nextlil 0 11 22 3 1 2 84.3模式匹配算法 §43模式匹配算法 void GetNext (char pll,int next){ ②考印却，则将求aext值的问题看成是模式匹配问题， 即P既为主串又为模式串 1求模式串P的next数组（递推法）i1-主串指针 将P右移，用next=k作下标，比较pp: i-1;j-0;next 1]-0; 即：令j-next[jl,如此反复比较prp m-P叫0：模式串长度 至pp(情况①)或者 while(ism)求nexti+1 j=0,令next+1-1为止/没有一个字符与p,比较 if (j=-0)next++il-++j;//next i+1]-1 例子自己分析 else /j>0 目标串： p1…Pt1…P-k1…P-1p if (Plil-Pljl) 模式串： next++i]-++j;//nexti+1]-j+l PP-k+1…P-1P else l/pP j-nextijl; 1可改进为书上一样的算法 §43模式匹配算法 §4.3模式匹配算法 时间：0(m) 即可用下述方式节省时间： 当p=p,时，将next置为nextk KMP算法的时间加上求nex数组后为O(+m) 此过程可重复！ 当>m时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时 例： 但当≈m时，朴素匹配可能更好 j1 2 3 4 5 jP next[j]nextvallj ■next数组的改进 Paaaab Ia 0 0 next性质5：若tp时，设next=k>0,应比较t~p 1 2 3 4 2a 1 0 尖叫 2 若已知p=p,则必有lpk,此时应使用next[k=k 0 P 4a3 0 (k>0)为下标继续比较：tP Px- 52014/4/7 5 §4.3 模式匹配算法 ④若P[1…j-1]不存在首尾相同的字符串，或者说仅存在长度为零的 相同前后缀（空串）子串，则k=1，即p1与ti 继续比较 特别地，若j=1（即ti ≠p1），则P中任何字符无法与ti 继续比较，P 右移1位，将p1和ti+1继续比较。按next定义，可取next[1]=0（对 任何P成立）。 综上所述，当ti ≠pj 时 25 0 j=1 P[1…j-1]中前后缀相等的最大真子串的长度加1(包括空串),即： Max{k|1≤k<j 且”p1…pk-1”=“pj-k+1…pj-1”} //k=1时,为空串 例： j 1 2 3 4 5 6 7 8 P a b a a b c a c next[j] 0 1 1 2 2 3 1 2 next[j]= §4.3 模式匹配算法  next数组生成（递推法） 设next[i]=j已知，求next[i+1] (i≥1) 由性质4告知我们，对任何模式P，总有next[1]=0 成立，给出了递推基础 ∵next[1]~next[i]已知，且已知next[i]=j ∴P[1 i 1]中有 26 P[1…i-1]中有： “p1…pj-1”=“pi-j+1…pi-1” //最大真子串长度为j-1 扩充一个字符pi 后，比较pj ~pi ①若pi =pj ，则P[1…j]=P[i-j+1…i] 即P[1…i]中前后缀的最大真子串长度为j，故 next[i+1]=j+1 或者 next[i+1]=next[i]+1 §4.3 模式匹配算法 ②若pi ≠pj ，则将求next值的问题看成是模式匹配问题， 即P既为主串又为模式串 将P右移，用next[j]=k作下标，比较pk~pi 即：令j←next[j]，如此反复比较pi ~pj 至pi =pj （情况①）或者 j=0，令next[i+1]=1为止 //没有一个字符与pi 比较 27 j ，令 [ ] 字符 pi 例子自己分析 ？ 目标串： p1…pi-j+1…pi-k+1…pi-1 pi … 模式串： p1……pj-k+1…pj-1 pj … p1……pk-1 pk §4.3 模式匹配算法 void GetNext (char p[] , int next[]) { //求模式串P的next数组（递推法）i-主串指针 i=1; j=0; next[1]=0; m=P[0]; //模式串长度 while (i<m) //求next[i+1] if (j==0) next[++i]=++j; //next[i+1]=1 28 if (j==0) next[++i]=++j; //next[i+1]=1 else //j>0 if (P[i]==P[j]) next[++i]=++j; //next[i+1]=j+1 else //pi ≠pj j=next[j]; } //可改进为书上一样的算法 §4.3 模式匹配算法 时间：O(m) KMP算法的时间加上求next数组后为O(n+m) 当n>>m时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时 29 但当n≈m时，朴素匹配可能更好 next数组的改进 next性质5：若ti ≠pj 时，设next[j]=k>0，应比较ti ~pk 若已知pk=pj ，则必有ti ≠pk，此时应使用next[k]=k’ (k’>0)为下标继续比较：ti ~pk’ §4.3 模式匹配算法 即可用下述方式节省时间： 当pj =pk时，将next[j]置为next[k] 此过程可重复！ 例： j 1 2 3 4 5 j P next[j] nextval[j] 30 j 1 2 3 4 5 j P next[j] nextval[j] P a a a a b 1 a 0 0 next[j] 0 1 2 3 4 2 a 1 0 改进 nextval[j] 0 0 0 0 4 3 a 2 0 pj p2 p3 p4 p5 4 a 3 0 pk p1p2 p3 p4 5 b 4 4 ti ≠p2,比较ti ~pnext[2] ∵p2=p1,next[2] ←next[1] ti ≠p3,ti ~pnext[3], ∵p3=p2∴next[3]←next[2]