lxy_CH4_2a

null第四章 串第四章 串串类型的定义 串的示和实现 串的模式匹配算法4.3 串的模式匹配子串的定位操作 int Index( S, T, pos) 称为串的模式匹配4.3 串的模式匹配Index操作的实现1Index操作的实现1int Index(String S, String T, int pos){ SposTmnIndex操作的实现1Index操作的实现1int Index(String S, String T, int pos){ STposnmi=posmSubIndex操作的实现1Index操作的实现1int Index(String S, String T, int pos){ STposnmi=pos+1mSubIndex操作的实现1Index操作的实现1int Index(String S, String T, int pos){ STposnmi=pos+2mSubIndex操作的实现1Index操作的实现1int Index(String S, String T, int pos){ STposnmi=n-m+1pos<=i0){ n=StrLength(S); m=StrLength(T); i=pos; while(i<=n-m+1){ SubString(sub,S,i,m); if(StrCompare(sub,T)!=0) ++i; else return i; //返回子串在主串中的位置 }//while }//if return 0; // S中不存在与T相等的子串 }//IndexIndex操作的实现1int Index(String S, String T, int pos){ nullababcabcacbababcaci=1j=11nullababcabcacbababcaci=2j=21nullababcabcacbababcaci=3j=31nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=3j=13nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=4j=23nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14ababcabcacbababcaci=5j=15nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14ababcabcacbababcaci=5j=15ababcabcacbababcaci=6j=16nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14ababcabcacbababcaci=5j=15ababcabcacbababcaci=6j=16nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14ababcabcacbababcaci=5j=15ababcabcacbababcaci=11j=66Index操作的实现2Index操作的实现2int Index(String S, String T, int pos){ STposnmi=n-m+1pos<=i=1&&pos<=S[0]){ k=i=pos; j=1; //i正文试配起点，j:模式指针，k:正文指针 last=S[0]-T[0]+1; //last:正文最后一个起点 while(k<=last && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=++k; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i; else return 0; } else return 0; }null模式匹配的一般过程i=i-j+2, j=1s1 s2  si-j+1 si-j+2  Si-1 si snp1 p2  pj-1 pj某次匹配Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }Brute-Force算法“蛮力”算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=1j=1ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=1j=1ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=1j=1ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=2ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=2ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=2ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=3ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=3ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=3ST第 1 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=3ST第 1 趟SBrute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=1ST第 2 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=1ST第 2 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=1ST第 2 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=1ST第 2 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=1ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=1ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=3j=1ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=2j=1ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=7j=5ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=7j=5ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=7j=5ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=7j=5ST第 3 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=4j=1ST第 4 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=5j=1ST第 5 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=6j=1ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=6j=1ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=6j=1ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=7j=2ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=10j=5ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=11j=6ST第 6 趟Brute-Force算法Brute-Force算法 int Index(SString S,SString T,int pos){ if(pos>=1&&pos<=S[0]){ i=pos; j=1; while(i<=S[0] && j<=T[0]) if(S[i]==T[j]) {++i; ++j; } // 继续比较后继字符 else{ i=i-j+2; j=1; } //指针后退重新开始匹配 if(j>T[0]) return i-T[0]; else return 0; } else return 0; }i=11j=6ST第 6 趟Brute-Force算法null1s1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pmnull12s1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pms1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pmnull12s1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pms1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pms1 s2  si  sm Sm+1  sn-m+1 sn-m+1  snp1 p2  pi  pmn-mO(m(n-m+1)) O(mn)nulls=“aaaa  aa”t=“aa  ab”nm每次比较字符数:m总共匹配次数:n-m+1O(m(n-m+1)) O(mn)最坏情况4.3.2 KMP算法4.3.2 KMP算法 1970年，S.A.Cook证明可用O(m+n)时间求解模式匹配问题 克努特（D.E.Knuth）和普拉特（V.R.Pratt）根据Cook的证明，构造出O(m+n)时间的模式匹配算法 同时，莫里斯(J.H.Morris)也

设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

出性能相似的算法当发现失配（sipj）时,正文指针i不回退，只让模式指针j回退,但不一定退回到1nullababcabcacbababcaci=3j=31ababcabcacbababcaci=2j=12ababcabcacbababcaci=7j=53ababcabcacbababci=4j=14ababcabcacbababcaci=5j=15ababcabcacbababcaci=11j=66nullababcabcacbababcaci=3j=31s1=p1s2=p2p1p2p1s2nullababcabcacbababcaci=3j=31ababcabcacbababcac2i=3j=1s1=p1s2=p2p1p2p1s2nullababcabcacbababcaci=3j=31ababcabcacbababcaci=7j=52si=pj (i=3~6, j=1~4)p1=p4s1=p1s2=p2p1p2p1s2nullababcabcacbababcaci=3j=31ababcabcacbababcaci=7j=52ababcabcacbababcaci=7j=23s1=p1s2=p2p1p2p1s2si=pj (i=3~6, j=1~4)p1=p4nullababcabcacbababcaci=3j=31ababcabcacbababcaci=7j=52ababcabcacbababcaci=11j=63si=pj (i=3~6, j=1~4)p1=p4s1=p1s2=p2p1p2p1s2nulls1 s2  si-j+1 si-j+2  Si-1 si snp1 p2  pj-1 pj(1) 模式串前j-1个字符全不相同p1  p2   pj-2  pj-1 (pjsi) 某次匹配p1  si-j+1, , p1  si-1null p1  pj-1 = si-j+1  si-1 (pjsi) (匹配结果)p1  pk-1 = pj-k+1  pj-1 (kT[0]) return i-T[0]; // 匹配成功 else return 0; }KMP模式匹配算法nullnext[j]函数的计算设next[j]=knext[1]=0(1) 若pk=pjnext[j+1]=k+1=next[j]+1null(2) 若pkpj设next[k]=k’ (0