6-5模式匹配v第六章查找技術(shù)模式匹配模式匹配的應(yīng)用場(chǎng)景1：模式匹配模式匹配的應(yīng)用場(chǎng)景2：模式匹配問(wèn)題有什么特點(diǎn)？（2）改進(jìn)取得的積累效益：模式匹配操作被頻繁調(diào)用，執(zhí)行頻率高。（1）算法的一次執(zhí)行時(shí)間：?jiǎn)栴}規(guī)模通常很大，常常在大量信息中進(jìn)行匹配；模式匹配（字符串匹配）：在主串S中尋找子串T

的過(guò)程，T也稱為模式S="s1s2…sn"T="t1t2…tm"如果匹配成功，返回T

在S

中的位置；否則返回0模式匹配BF算法KMP算法6-5-1BF算法v第六章查找技術(shù)基本思想1.在串S和串T中設(shè)比較的起始下標(biāo)i和j；2.循環(huán)直到S或T的所有字符均比較完2.1如果S[i]等于T[j]，繼續(xù)比較S和T的下一個(gè)字符；2.2否則，將i和j回溯，準(zhǔn)備下一趟比較；3.如果T中所有字符均比較完，則返回匹配的起始比較下標(biāo)；否則返回0；ji…ij

主串Ss1s2si

sn模式T

t1t2tjij例1主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=2失??；i回溯到1，j回溯到0ijijij第1趟abcac運(yùn)行實(shí)例i=1，j=0失?。籭回溯到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"運(yùn)行實(shí)例例1主串S="ababcabcacbab"，模式T="abcac"運(yùn)行實(shí)例ababcabcacbabij第5趟abcaci=4，j=0失敗i回溯到5，j回溯到0ijababcabcacbab第6趟abcaci=10，j=5，T中全部字符都比較完畢，匹配成功算法實(shí)現(xiàn)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"在匹配成功的情況下，考慮兩種極端情況：設(shè)匹配成功發(fā)生在si處，則：例如：S="aaaaaaaaaabcdccccc"T="bcd"最好情況：不成功的匹配都發(fā)生在串T

的第1個(gè)字符設(shè)匹配成功發(fā)生在si處，則：例如：S="aaaaaaaaaaaabccccc"T="aaab"最壞情況：不成功的匹配都發(fā)生在串T

的最后一個(gè)字符性能分析S="s1s2…sn"T="t1t2…tm"在匹配成功的情況下，考慮兩種極端情況：分析BF算法為什么BF算法的性能較低？ji…ij

主串Ss1s2si

sn模式T

t1t2tj在每趟匹配不成功時(shí)存在大量回溯，沒(méi)有利用已經(jīng)部分匹配的結(jié)果如何在匹配不成功時(shí)主串不回溯？主串不回溯，模式就需要向右滑動(dòng)一段距離i模式T

t1t2tj如何確定模式的滑動(dòng)距離？分析BF算法如何在匹配不成功時(shí)主串不回溯？主串不回溯，模式就需要向右滑動(dòng)一段距離

主串Ss1s2si

snababcabcacbabij第1趟a

bcac

i=2，j=2失?。?/p>

∵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算法結(jié)論：i可以不回溯，模式向右滑動(dòng)到新的比較起點(diǎn)k如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)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算法結(jié)論：i可以不回溯，模式向右滑動(dòng)到新的比較起點(diǎn)k如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)k？長(zhǎng)度為k的前綴（1）k與j具有函數(shù)關(guān)系，由當(dāng)前失配位置j，可以計(jì)算出滑動(dòng)位置kT[0]~T[k-1]=T[j-k]~T[j-1]說(shuō)明了什么？T[0]~T[k-1]=T[j-k]~T[j-1]的物理意義是什么？長(zhǎng)度為k的后綴T[0]~T[j]中前綴和后綴相等的真子串唯一嗎?（2）滑動(dòng)位置k僅與模式串T有關(guān)ababac

ababac

ababac

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

且T[0]…T[k-1]=T[j-k]…T[j-1]}模式應(yīng)該向右滑多遠(yuǎn)才能保證算法的正確性?abababacijababacabababacijababacabababacababacijk=1:k=3:KMP算法失效數(shù)組-1j=0max{k|1≤k＜j

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

…T[j-1]}集合非空0其它情況next[j]=設(shè)next[j]表示在匹配過(guò)程中與T[j]比較不相等時(shí)，下標(biāo)j的回溯位置下標(biāo)：01234模式串T：ababck=next[j]：

j=0時(shí),k＝-1j=1時(shí),k＝0-10j=2時(shí),T[0]≠T[1]，因此，k=00j=3時(shí),T[0]＝T[2]，T[0]T[1]≠T[1]T[2]，因此，k=11j=4時(shí),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運(yùn)行實(shí)例ababaabab