数据结构-从概念到C++实现（第4版）课件 6-5模式匹配

6-5模式匹配v第六章查找技术模式匹配模式匹配的应用场景1：模式匹配模式匹配的应用场景2：模式匹配问题有什么特点？（2）改进取得的积累效益：模式匹配操作被频繁调用，执行频率高。（1）算法的一次执行时间：问题规模通常很大，常常在大量信息中进行匹配；模式匹配（字符串匹配）：在主串S中寻找子串T

的过程，T也称为模式S="s1s2…sn"T="t1t2…tm"如果匹配成功，返回T

在S

中的位置；否则返回0模式匹配BF算法KMP算法6-5-1BF算法v第六章查找技术基本思想1.在串S和串T中设比较的起始下标i和j；2.循环直到S或T的所有字符均比较完2.1如果S[i]等于T[j]，继续比较S和T的下一个字符；2.2否则，将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则返回匹配的起始比较下标；否则返回0；ji…ij

主串Ss1s2si

sn模式T

t1t2tjij例1主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=2失败；i回溯到1，j回溯到0ijijij第1趟abcac运行实例i=1，j=0失败；i回溯到2，j回溯到0ababcabcacbab第2趟abcaciji=6，j=4失败i回溯到3，j回溯到0ababcabcacbabij第3趟abcacababcabcacbab第4趟abcaciji=3，j=0失败i回溯到4，j回溯到0例1主串S="ababcabcacbab"，模式T="abcac"运行实例例1主串S="ababcabcacbab"，模式T="abcac"运行实例ababcabcacbabij第5趟abcaci=4，j=0失败i回溯到5，j回溯到0ijababcabcacbab第6趟abcaci=10，j=5，T中全部字符都比较完毕，匹配成功算法实现intBF(charS[],charT[]){inti=0,j=0;

while(S[i]!='\0'&&T[j]!='\0'){if(S[i]==T[j]){i++;j++;}else{i=i–j+1;j=0;}}

if(T[j]=='\0')return(i–j+1);

elsereturn0;}intBF(charS[],charT[]){inti=0,j=0,start=0;

while(S[i]!='\0’&&T[j]!='\0'){if(S[i]==T[j]){i++;j++;}else{

start++;i=start;j=0;}}

if(T[j]=='\0')returnstart+1;

elsereturn0;}性能分析S="s1s2…sn"T="t1t2…tm"在匹配成功的情况下，考虑两种极端情况：设匹配成功发生在si处，则：例如：S="aaaaaaaaaabcdccccc"T="bcd"最好情况：不成功的匹配都发生在串T

的第1个字符设匹配成功发生在si处，则：例如：S="aaaaaaaaaaaabccccc"T="aaab"最坏情况：不成功的匹配都发生在串T

的最后一个字符性能分析S="s1s2…sn"T="t1t2…tm"在匹配成功的情况下，考虑两种极端情况：分析BF算法为什么BF算法的性能较低？ji…ij

主串Ss1s2si

sn模式T

t1t2tj在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离i模式T

t1t2tj如何确定模式的滑动距离？分析BF算法如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离

主串Ss1s2si

snababcabcacbabij第1趟a

bcac

i=2，j=2失败；

∵s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]ababcabcacbab第2趟abcac

分析BF算法ababcabcacbabij第1趟abcac

i=2，j=2失败；

∵s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]ababcabcacbabi第3趟jabcac

分析BF算法ababcabcacbab第3趟a

bcac

iji=6，j=4失败∵s[3]=t[1];t[0]≠t[1]∴t[0]≠s[3]ababcabcacbab第4趟abcac

分析BF算法ababcabcacbab第3趟abcac

iji=6，j=4失败∵s[4]=t[2];t[0]≠t[2]∴t[0]≠s[4]ababcabcacbab第5趟abcac

分析BF算法ababcabcacbab第3趟abcac

iji=6，j=4失败∵s[4]=t[2];t[0]≠t[2]∴t[0]≠s[4]ababcabcacbab第6趟abcac

iji=6，j=4失败∵s[5]=t[3];t[0]=t[3]∴t[0]=s[5]分析BF算法KMP算法结论：i可以不回溯，模式向右滑动到新的比较起点k如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ababcab…abcac

ijabcac

ababcab…ik下一趟（1）T[0]~T[k-1]=S[i-k]~S[i-1]ababcab…abcac

ijabcac

ababcab…ik下一趟（1）T[0]~T[k-1]=S[i-k]~S[i-1]（2）T[j-k]~T[j-1]=S[i-k]~S[i-1]T[0]~T[k-1]=T[j-k]~T[j-1]KMP算法结论：i可以不回溯，模式向右滑动到新的比较起点k如何由当前部分匹配结果确定模式向右滑动的新比较起点k？长度为k的前缀（1）k与j具有函数关系，由当前失配位置j，可以计算出滑动位置kT[0]~T[k-1]=T[j-k]~T[j-1]说明了什么？T[0]~T[k-1]=T[j-k]~T[j-1]的物理意义是什么？长度为k的后缀T[0]~T[j]中前缀和后缀相等的真子串唯一吗?（2）滑动位置k仅与模式串T有关ababac

ababac

ababac

k=1k=3KMP算法max{k|1≤k＜j

且T[0]…T[k-1]=T[j-k]…T[j-1]}模式应该向右滑多远才能保证算法的正确性?abababacijababacabababacijababacabababacababacijk=1:k=3:KMP算法失效数组-1j=0max{k|1≤k＜j

且T[0]…T[k-1]=T[j-k]

…T[j-1]}集合非空0其它情况next[j]=设next[j]表示在匹配过程中与T[j]比较不相等时，下标j的回溯位置下标：01234模式串T：ababck=next[j]：

j=0时,k＝-1j=1时,k＝0-10j=2时,T[0]≠T[1]，因此，k=00j=3时,T[0]＝T[2]，T[0]T[1]≠T[1]T[2]，因此，k=11j=4时,T[0]≠T[3]，T[0]T[1]=T[2]T[3]，T[0]T[1]T[2]≠T[1]T[2]T[3]，因此，k=22ababaababcb

i=4，j=4失败；

j=next[4]=2ij第1趟ababcnext[j]={-1,0,0,1,2}ababaababcb

ij第2趟ababc运行实例ababaabab