操屁眼的视频在线免费看,日本在线综合一区二区,久久在线观看免费视频,欧美日韩精品久久综

快速模式匹配算法，簡(jiǎn)稱(chēng)KMP 算法，是在 BF 算法基礎(chǔ)上改進(jìn)得到的算法。學(xué)習(xí) BF 算法我們知道，該算法的實(shí)現(xiàn)過(guò)程就是 "傻瓜式" 地用模式串（假定為子串的串）與主串中的字符一一匹配，算法執(zhí)行效率不高。

KMP 算法不同，它的實(shí)現(xiàn)過(guò)程接近人為進(jìn)行模式匹配的過(guò)程。例如，對(duì)主串 A（""）和模式串 B（"ABCE"）進(jìn)行模式匹配，如果人為去判斷，僅需匹配兩次。

圖 1 第一次人為模式匹配

第一次如圖 1 所示，最終匹配失敗。但在本次匹配過(guò)程中，我們可以獲得一些信息，模式串中 "ABC" 都和主串對(duì)應(yīng)的字符相同，但模式串中字符 'A' 與 'B' 和 'C' 不同。

因此進(jìn)行下次模式匹配時(shí)，沒(méi)有必要讓串 B 中的 'A' 與主串中的字符 'B' 和 'C' 一一匹配（它們絕不可能相同），而是直接去匹配失敗位置處的字符 'A' ，如圖 2 所示：

圖 2 第二次人為模式匹配

至此，匹配成功。若使用 BF 算法，則此模式匹配過(guò)程需要進(jìn)行 4 次。

由此可以看出，每次匹配失敗后模式串移動(dòng)的距離不一定是 1，某些情況下一次可移動(dòng)多個(gè)位置，這就是 KMP 模式匹配算法。

那么，如何判斷匹配失敗后模式串向后移動(dòng)的距離呢？

模式串移動(dòng)距離的判斷每次模式匹配失敗后，計(jì)算模式串向后移動(dòng)的距離是 KMP 算法中的核心部分。

其實(shí)，匹配失敗后模式串移動(dòng)的距離和主串沒(méi)有關(guān)系，只與模式串本身有關(guān)系。

例如，我們將前面的模式串 B 改為 "ABCAE"c語(yǔ)音的模式匹配算法，則在第一次模式匹配失敗，由于匹配失敗位置模式串中字符 'E' 前面有兩個(gè)字符 'A'，因此，第二次模式匹配應(yīng)改為如圖 3 所示的位置：

圖 3 模式匹配過(guò)程示意圖

結(jié)合圖 1、圖 2 和圖 3 不難看出，模式串移動(dòng)的距離只和自身有關(guān)系，和主串無(wú)關(guān)。換句話(huà)說(shuō)，不論主串如何變換，只要給定模式串，則匹配失敗后移動(dòng)的距離就已經(jīng)確定了。

不僅如此，模式串中任何一個(gè)字符都可能導(dǎo)致匹配失敗，因此串中每個(gè)字符都應(yīng)該對(duì)應(yīng)一個(gè)數(shù)字，用來(lái)表示匹配失敗后模式串移動(dòng)的距離。

注意，這里要轉(zhuǎn)換一下思想，模式串向后移動(dòng)等價(jià)于指針 j 前移，如圖 4 中的 a) 和 b)。換句話(huà)說(shuō)，模式串后移相當(dāng)于對(duì)指針 j 重定位。

圖 4 模式串后移等價(jià)于 j 前移

因此，我們可以給每個(gè)模式串配備一個(gè)數(shù)組（例如 next[]），用于存儲(chǔ)模式串中每個(gè)字符對(duì)應(yīng)指針 j 重定向的位置（也就是存儲(chǔ)模式串的數(shù)組下標(biāo)），比如 j=3，則該字符匹配失敗后指針 j 指向模式串中第 3 個(gè)字符。

模式串中各字符對(duì)應(yīng) next 值的計(jì)算方式是，取該字符前面的字符串（不包含自己），其前綴字符串和后綴字符串相同字符的最大個(gè)數(shù)再 +1 就是該字符對(duì)應(yīng)的 next 值。

前綴字符串指的是位于模式串起始位置的字符串，例如模式串 "ABCD"，則 "A"、"AB"、"ABC" 以及 "ABCD" 都屬于前綴字符串；后綴字符串指的是位于串結(jié)尾處的字符串，還拿模式串 "ABCD" 來(lái)說(shuō)，"D"、"CD"、"BCD" 和 "ABCD" 為后綴字符串。注意，模式串中第一個(gè)字符對(duì)應(yīng)的值為 0，第二個(gè)字符對(duì)應(yīng) 1 ，這是固定不變的（先這么認(rèn)為）。因此c語(yǔ)音的模式匹配算法，圖 3 的模式串 "ABCAE" 中，各字符對(duì)應(yīng)的 next 值如圖 5 所示：

圖 5 模式串對(duì)應(yīng)的 next 數(shù)組

從圖 5 中的數(shù)據(jù)可以看出，當(dāng)字符 'E' 匹配失敗時(shí)，指針 j 指向模式串?dāng)?shù)組中第 2 個(gè)字符，即 'B'，同之前講解的圖 3 不謀而合。

以上所講 next 數(shù)組的實(shí)現(xiàn)方式是為了讓大家對(duì)此數(shù)組的功能有一個(gè)初步的認(rèn)識(shí)。接下來(lái)學(xué)習(xí)如何用編程的思想實(shí)現(xiàn) next 數(shù)組。編程實(shí)現(xiàn) next 數(shù)組要解決的主要問(wèn)題依然是 "如何計(jì)算每個(gè)字符前面前綴字符串和后綴字符串相同的個(gè)數(shù)"。

仔細(xì)觀察圖 5，為什么字符 'C' 對(duì)應(yīng)的 next 值為 1？因?yàn)樽址?"AB" 前綴字符串和后綴字符串相等個(gè)數(shù)為 0，0 + 1 = 1。那么，為什么字符 'E' 的 next 值為 2？因?yàn)榫o挨著該字符之前的 'A' 與模式串開(kāi)頭字符 'A' 相等，1 + 1 = 2。

如果圖 5 中模式串為 ""，則對(duì)應(yīng) next 數(shù)組應(yīng)為 [0,1,1,1,2,3]，為什么字符 'E' 的 next 值是 3 ？因?yàn)榫o挨著該字符前面的 "AB" 與開(kāi)頭的 "AB" 相等，2 + 1 =3。

因此，我們可以設(shè)計(jì)這樣一個(gè)算法，剛開(kāi)始時(shí)令 j 指向模式串中第 1 個(gè)字符（j=1），i 指向第 2 個(gè)字符（i=2）。接下來(lái)，對(duì)每個(gè)字符做如下操作：

如果 i 和 j 指向的字符相等，則 i 后面第一個(gè)字符的 next 值為 j+1，同時(shí) i 和 j 做自加 1 操作，為求下一個(gè)字符的 next 值做準(zhǔn)備，如圖 6 所示：

圖 6 i 和 j 指向字符相等

上圖中可以看到，字符 'a' 的 next 值為 j +1 = 2，同時(shí) i 和 j 都做了加 1 操作（此時(shí) j=2，i=3）。當(dāng)計(jì)算字符 'C' 的 next 值時(shí)，還是判斷 i 和 j 指向的字符是否相等，顯然相等，因此令該字符串的 next 值為 j + 1 = 3，同時(shí) i 和 j 自加 1（此次 next 值的計(jì)算使用了上一次 j 的值）。如圖 7 所示：

圖 7 i 和 j 指向字符仍相等

如上圖所示，計(jì)算字符 'd' 的 next 時(shí)，i 和 j 指向的字符不相等（此時(shí) j=3，i=4），這表明最長(zhǎng)的前綴字符串 "aaa" 和后綴字符串 "aac" 不相等，接下來(lái)要判斷次長(zhǎng)的前綴字符串 "aa" 和后綴字符串 "ac" 是否相等，這一步的實(shí)現(xiàn)可以用 j = next[j] 來(lái)實(shí)現(xiàn)（注意，next 數(shù)組從下標(biāo) 1 開(kāi)始使用，舍棄 next[0] ），如圖 8 所示：

圖 8 執(zhí)行 j=next[j] 操作

從上圖可以看到，i 和 j 指向的字符又不相同，因此繼續(xù)做 j = next[j] 的操作，如圖 9 所示：

圖 9 繼續(xù)執(zhí)行 j=next[j] 的操作

此時(shí)，由于 j 和 i 指向的字符仍不相等，繼續(xù)執(zhí)行 j=next[j] 得到 j=0，這意味著字符 'd' 前的前綴字符串和后綴字符串相同個(gè)數(shù)為 0，因此如果字符 'd' 導(dǎo)致了模式匹配失敗，則模式串移動(dòng)的距離只能是 1。

這里給出使用上述思想實(shí)現(xiàn) next 數(shù)組的 C 語(yǔ)言代碼：

void Next(char*T,int *next){    next[1]=0;    int i=1;    int j=0;    //next[2]=1 可以通過(guò)第一次循環(huán)直接得出    while (i<strlen(T)) {        if (j==0||T[i-1]==T[j-1]) {            i++;            j++;            next[i]=j;        }else{            j=next[j];        }    }}

代碼中 j=next[j] 的運(yùn)用可以這樣理解，每個(gè)字符對(duì)應(yīng)的next值都可以表示該字符前 "同后綴字符串相同的前綴字符串最后一個(gè)字符所在的位置"，因此在每次匹配失敗后，都可以輕松找到次長(zhǎng)前綴字符串的最后一個(gè)字符與該字符進(jìn)行比較。Next函數(shù)的缺陷
圖 10 Next 函數(shù)的缺陷
例如，在圖 10a) 中，當(dāng)匹配失敗時(shí)，Next 函數(shù)會(huì)由圖 10b) 開(kāi)始繼續(xù)進(jìn)行模式匹配，但是從圖中可以看到，這樣做是沒(méi)有必要的，純屬浪費(fèi)時(shí)間。
出現(xiàn)這種多余的操作，問(wèn)題在當(dāng) T[i-1]==T[j-1] 成立時(shí)，沒(méi)有繼續(xù)對(duì) i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進(jìn)后的 Next 函數(shù)如下所示：
void Next(char*T,int *next){     next[1]=0;    int i=1;    int j=0;    while (i        if (j==0||T[i-1]==T[j-1]) {            i++;            j++;            if (T[i-1]!=T[j-1]) {               next[i]=j;            }            else{                next[i]=next[j];            }        }else{            j=next[j];        }    }}

注意，這里只設(shè)定了 next[1] 的值為 0，而 next[1] 的值，需要經(jīng)過(guò)判斷之后，才能最終得出，所以它的值不一定是 1。
使用精簡(jiǎn)過(guò)后的 next 數(shù)組在解決例如模式串為 "" 這類(lèi)的問(wèn)題上，會(huì)大大提高效率，如圖 11 所示，精簡(jiǎn)前為 next1，精簡(jiǎn)后為 next2：
圖 11 改進(jìn)后的 Next 函數(shù)KMP 算法的實(shí)現(xiàn)假設(shè)主串 A 為 ""，模式串 B 為 "abcac"，則 KMP 算法執(zhí)行過(guò)程為：
很明顯，使用 KMP 算法只需匹配 3 次，而同樣的問(wèn)題使用 BF 算法則需匹配 6 次才能完成。
KMP 算法的完整 C 語(yǔ)言實(shí)現(xiàn)代碼為：
運(yùn)行結(jié)果為：
#include #include //調(diào)用了普通求 next 的方式，這里并未直接對(duì) next[1] 賦值為 1，但通過(guò)函數(shù)第一次運(yùn)行，也可以得出它的值為 1void Next(char*T,int *next){    int i=1;    next[1]=0;    int j=0;    while (i<strlen(T)) {        if (j==0||T[i-1]==T[j-1]) {            i++;            j++;            next[i]=j;        }else{            j=next[j];        }    }}int KMP(char * S,char * T){    int next[10];    Next(T,next);//根據(jù)模式串T,初始化next數(shù)組    int i=1;    int j=1;    while (i<=strlen(S)&&j<=strlen(T)) {        //j==0:代表模式串的第一個(gè)字符就和當(dāng)前測(cè)試的字符不相等；S[i-1]==T[j-1],如果對(duì)應(yīng)位置字符相等，兩種情況下，指向當(dāng)前測(cè)試的兩個(gè)指針下標(biāo)i和j都向后移        if (j==0 || S[i-1]==T[j-1]) {            i++;            j++;        }        else{            j=next[j];//如果測(cè)試的兩個(gè)字符不相等，i不動(dòng)，j變?yōu)楫?dāng)前測(cè)試字符串的next值        }    }    if (j>strlen(T)) {//如果條件為真，說(shuō)明匹配成功        return i-(int)strlen(T);    }    return -1;}int main() {    int i=KMP("ababcabcacbab","abcac");    printf("%d",i);    return 0;}

6