快速模式匹配算法(KMP)的深入理解
更新時(shí)間:2013年05月29日 09:26:08 作者:
本篇文章是對(duì)快速模式匹配算法(KMP)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
恐怕現(xiàn)在用過(guò)電腦的人,一定都知道大部分帶文本編輯功能的軟件都有一個(gè)快捷鍵ctrl+f 吧(比如word)。這個(gè)功能主要來(lái)完成“查找”,“替換”和“全部替換”功能的,其實(shí)這就是典型的模式匹配的應(yīng)用,即在文本文件中查找串。
1.模式匹配
模式匹配的模型大概是這樣的:給定兩個(gè)字符串變量S和P,其中S成為目標(biāo)串,其中包含n個(gè)字符,P稱為模式串,包含m個(gè)字符,其中m<=n。從S的給定位置(通常是S的第一個(gè)位置)開(kāi)始搜索模式P。如果找到,則返回模式P在目標(biāo)串中的位置(即:P的第一個(gè)字符在S中的下標(biāo))。如果在目標(biāo)串S中沒(méi)有找到模式串P,則返回-1.這就是模式匹配的定義啦,下面來(lái)看看怎么實(shí)現(xiàn)模式匹配算法吧。
2.樸素的模式匹配
樸素的模式匹配算法非常簡(jiǎn)單,容易理解,大概思路是這樣的:從S的第一個(gè)字符S0開(kāi)始,將P中的字符依次和S中字符比較,若S0=P0 && …… && Sm-1 = Pm-1,則證明匹配成功,剩下的匹配無(wú)需進(jìn)行了,返回下標(biāo)0。若在某一步Si != Pi 則P中剩下的字符也不用比較了,不可能匹配成功了,然后從S中第二個(gè)字符開(kāi)始與P中第一個(gè)字符進(jìn)行比較,同理,也是知道Sm = Pm-1或者找到某個(gè)i使得Si != S-1為止。依次類推若知道以S中第n-m個(gè)開(kāi)始字符為止,還沒(méi)有匹配成功則證明S中不存模式P。(想想為什么這里強(qiáng)調(diào)是n-m)這個(gè)代碼實(shí)現(xiàn)應(yīng)該是非常簡(jiǎn)單的,具體開(kāi)始參考strstr函數(shù)的內(nèi)部實(shí)現(xiàn)??梢钥纯窗俣劝倏?,給個(gè)鏈接http://baike.baidu.com/view/745156.htm,這里不寫出來(lái)了,還得趕緊進(jìn)入正題KMP呢。
3.快速模式匹配算法(KMP)
樸素的模式匹配效率不高的主要原因是進(jìn)行了重復(fù)的字符比較。下一次比較和上一次比較沒(méi)有任何的聯(lián)系,是樸素模式匹配的缺點(diǎn),其實(shí)上一次比較的比較結(jié)果是可以利用的,這就產(chǎn)生了快速模式匹配。在樸素的模式匹配中,目標(biāo)串S的下標(biāo)移動(dòng)是一步一步的,這其實(shí)并不好,移動(dòng)步數(shù)沒(méi)有必要為1。
現(xiàn)在不妨假設(shè),當(dāng)前匹配情況是這樣的:S0 …… St St+1 …… St+j 與 P0 P1…… Pj ,現(xiàn)在正在嘗試匹配的字符是St+j+1和Pj+1,并且St+j+1 != Pj+1,言外之意就是說(shuō)St St+1……St+j和P0 P1……Pj是完全匹配的。那么這個(gè)時(shí)候,S中下一次匹配開(kāi)始位置應(yīng)該是什么呢??按照樸素的模式匹配,下次比較應(yīng)該從St+1開(kāi)始,并且令St+1和P0比較,但是在快速模式匹配中并不是這樣,快速模式匹配選擇St+j+1和Pk+1比較,K是什么呢?K是這樣的一個(gè)值,使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配,不妨設(shè)k=next[j],因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要進(jìn)行匹配的兩個(gè)字符應(yīng)為St+j+1和Pk+1。S和P都沒(méi)有回溯到下標(biāo)0在進(jìn)行比較,這就是KMP之所以快的原因啦。
現(xiàn)在關(guān)鍵問(wèn)題來(lái)了,這個(gè)K怎么能得到呢?如果得到這個(gè)K值復(fù)雜度高,那這個(gè)思路就不好了,其實(shí)這個(gè)K呢,只和模式串P有關(guān)系,并且要求m個(gè)k,k = next[j],因此只要算一次存儲(chǔ)到next數(shù)組中就可以了,并且時(shí)間復(fù)雜度和m有關(guān)系(線性關(guān)系)??纯淳唧w怎么求next數(shù)組的值,即求k。
用歸納法求next[]:設(shè)next(0) = -1,若已知next(j) = k,欲求得next[j+1]。
(1)如果Pk+1 = Pj+1,顯然next[j+1] = k+1.如果Pk+1 != Pj+1,則next[j+1] < next[j],于是尋找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是說(shuō)h = next(k);看出來(lái)了吧,這是個(gè)迭代的過(guò)程。(也就是以前的結(jié)果對(duì)求以后的值有用)
(2)如果不存這樣的h,說(shuō)明P0 P1……Pj+1中沒(méi)有前后相等的子串,因此next[j+1] =-1.
(3)如果存在這樣的h,繼續(xù)檢驗(yàn)Ph和Pj是否相等。知道找到這中相等的情況,或者確定為-1求next[j+1]的過(guò)程結(jié)束。
看看實(shí)現(xiàn)的代碼:
View Code
int next[20] ={0};
//注意返回結(jié)果是一個(gè)數(shù)組next,保存m個(gè)k值得地方,即若next[j]=k
//則str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
//這樣當(dāng)des[t+j+1]和pat[j+1]匹配失敗時(shí),下一個(gè)匹配位置為des[t+j+1]和next[j]+1
void Next(char str[],int len)
{
next[0] = -1;
for(int j = 1 ; j < len ; j++)
{
int i = next[j-1];
while(str[j] != str[i+1] && i >= 0)//迭代的過(guò)程
{
i = next[i];
}
if(str[j] == str[i+1])
{
next[j] = i+1;
}
else
{
next[j] = -1;
}
}
}
現(xiàn)在有了next數(shù)組保存的k值,就可以實(shí)現(xiàn)KMP算法了:
View Code
//des是目標(biāo)串,pat是模式串,len1和len2是串的長(zhǎng)度
int kmp(char des[],int len1,char pat[],int len2)
{
Next(str2,len2);
int p=0,s=0;
while(p < len2 && s < len1)
{
if(pat[p] == des[s])
{
p++;s++;
}
else
{
if(p==0)
{
s++;//若第一個(gè)字符就匹配失敗,則從des的下一個(gè)字符開(kāi)始
}
else
{
p = next[p-1]+1;//用失敗函數(shù)確定pat應(yīng)回溯到的字符
}
}
}
if(p < len2)//整個(gè)過(guò)程匹配失敗
{
return -1;
}
return s-len2;
}
時(shí)間復(fù)雜度:
對(duì)于Next函數(shù)近似接近O(m),KMP算法的時(shí)間復(fù)雜度為O(n),所以整個(gè)算法的時(shí)間復(fù)雜度為O(n+m)
空間復(fù)雜度:
多引入了O(m)的空間復(fù)雜度。
4.應(yīng)用KMP的一道面試題
給定兩個(gè)字符串是s1和s2,要判定s2是否能夠被s1做循環(huán)移位得到的字符串包含。例如s1=AABCD,s2 =CDAA,返回true,因?yàn)閟1循環(huán)移位可以變成CDAAB。給定s1=ACBD和s2=ACBD則返回false。
分析:不難發(fā)現(xiàn)對(duì)s2移位得到的字符串都將是字符串s1s1的子串,如果s2可以有s1循環(huán)移位得到,那么s2一定是s1s1的子串,這時(shí)KMP算法是不是就很管用了呢。
1.模式匹配
模式匹配的模型大概是這樣的:給定兩個(gè)字符串變量S和P,其中S成為目標(biāo)串,其中包含n個(gè)字符,P稱為模式串,包含m個(gè)字符,其中m<=n。從S的給定位置(通常是S的第一個(gè)位置)開(kāi)始搜索模式P。如果找到,則返回模式P在目標(biāo)串中的位置(即:P的第一個(gè)字符在S中的下標(biāo))。如果在目標(biāo)串S中沒(méi)有找到模式串P,則返回-1.這就是模式匹配的定義啦,下面來(lái)看看怎么實(shí)現(xiàn)模式匹配算法吧。
2.樸素的模式匹配
樸素的模式匹配算法非常簡(jiǎn)單,容易理解,大概思路是這樣的:從S的第一個(gè)字符S0開(kāi)始,將P中的字符依次和S中字符比較,若S0=P0 && …… && Sm-1 = Pm-1,則證明匹配成功,剩下的匹配無(wú)需進(jìn)行了,返回下標(biāo)0。若在某一步Si != Pi 則P中剩下的字符也不用比較了,不可能匹配成功了,然后從S中第二個(gè)字符開(kāi)始與P中第一個(gè)字符進(jìn)行比較,同理,也是知道Sm = Pm-1或者找到某個(gè)i使得Si != S-1為止。依次類推若知道以S中第n-m個(gè)開(kāi)始字符為止,還沒(méi)有匹配成功則證明S中不存模式P。(想想為什么這里強(qiáng)調(diào)是n-m)這個(gè)代碼實(shí)現(xiàn)應(yīng)該是非常簡(jiǎn)單的,具體開(kāi)始參考strstr函數(shù)的內(nèi)部實(shí)現(xiàn)??梢钥纯窗俣劝倏?,給個(gè)鏈接http://baike.baidu.com/view/745156.htm,這里不寫出來(lái)了,還得趕緊進(jìn)入正題KMP呢。
3.快速模式匹配算法(KMP)
樸素的模式匹配效率不高的主要原因是進(jìn)行了重復(fù)的字符比較。下一次比較和上一次比較沒(méi)有任何的聯(lián)系,是樸素模式匹配的缺點(diǎn),其實(shí)上一次比較的比較結(jié)果是可以利用的,這就產(chǎn)生了快速模式匹配。在樸素的模式匹配中,目標(biāo)串S的下標(biāo)移動(dòng)是一步一步的,這其實(shí)并不好,移動(dòng)步數(shù)沒(méi)有必要為1。
現(xiàn)在不妨假設(shè),當(dāng)前匹配情況是這樣的:S0 …… St St+1 …… St+j 與 P0 P1…… Pj ,現(xiàn)在正在嘗試匹配的字符是St+j+1和Pj+1,并且St+j+1 != Pj+1,言外之意就是說(shuō)St St+1……St+j和P0 P1……Pj是完全匹配的。那么這個(gè)時(shí)候,S中下一次匹配開(kāi)始位置應(yīng)該是什么呢??按照樸素的模式匹配,下次比較應(yīng)該從St+1開(kāi)始,并且令St+1和P0比較,但是在快速模式匹配中并不是這樣,快速模式匹配選擇St+j+1和Pk+1比較,K是什么呢?K是這樣的一個(gè)值,使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配,不妨設(shè)k=next[j],因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要進(jìn)行匹配的兩個(gè)字符應(yīng)為St+j+1和Pk+1。S和P都沒(méi)有回溯到下標(biāo)0在進(jìn)行比較,這就是KMP之所以快的原因啦。
現(xiàn)在關(guān)鍵問(wèn)題來(lái)了,這個(gè)K怎么能得到呢?如果得到這個(gè)K值復(fù)雜度高,那這個(gè)思路就不好了,其實(shí)這個(gè)K呢,只和模式串P有關(guān)系,并且要求m個(gè)k,k = next[j],因此只要算一次存儲(chǔ)到next數(shù)組中就可以了,并且時(shí)間復(fù)雜度和m有關(guān)系(線性關(guān)系)??纯淳唧w怎么求next數(shù)組的值,即求k。
用歸納法求next[]:設(shè)next(0) = -1,若已知next(j) = k,欲求得next[j+1]。
(1)如果Pk+1 = Pj+1,顯然next[j+1] = k+1.如果Pk+1 != Pj+1,則next[j+1] < next[j],于是尋找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是說(shuō)h = next(k);看出來(lái)了吧,這是個(gè)迭代的過(guò)程。(也就是以前的結(jié)果對(duì)求以后的值有用)
(2)如果不存這樣的h,說(shuō)明P0 P1……Pj+1中沒(méi)有前后相等的子串,因此next[j+1] =-1.
(3)如果存在這樣的h,繼續(xù)檢驗(yàn)Ph和Pj是否相等。知道找到這中相等的情況,或者確定為-1求next[j+1]的過(guò)程結(jié)束。
看看實(shí)現(xiàn)的代碼:
復(fù)制代碼 代碼如下:
View Code
int next[20] ={0};
//注意返回結(jié)果是一個(gè)數(shù)組next,保存m個(gè)k值得地方,即若next[j]=k
//則str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
//這樣當(dāng)des[t+j+1]和pat[j+1]匹配失敗時(shí),下一個(gè)匹配位置為des[t+j+1]和next[j]+1
void Next(char str[],int len)
{
next[0] = -1;
for(int j = 1 ; j < len ; j++)
{
int i = next[j-1];
while(str[j] != str[i+1] && i >= 0)//迭代的過(guò)程
{
i = next[i];
}
if(str[j] == str[i+1])
{
next[j] = i+1;
}
else
{
next[j] = -1;
}
}
}
現(xiàn)在有了next數(shù)組保存的k值,就可以實(shí)現(xiàn)KMP算法了:
復(fù)制代碼 代碼如下:
View Code
//des是目標(biāo)串,pat是模式串,len1和len2是串的長(zhǎng)度
int kmp(char des[],int len1,char pat[],int len2)
{
Next(str2,len2);
int p=0,s=0;
while(p < len2 && s < len1)
{
if(pat[p] == des[s])
{
p++;s++;
}
else
{
if(p==0)
{
s++;//若第一個(gè)字符就匹配失敗,則從des的下一個(gè)字符開(kāi)始
}
else
{
p = next[p-1]+1;//用失敗函數(shù)確定pat應(yīng)回溯到的字符
}
}
}
if(p < len2)//整個(gè)過(guò)程匹配失敗
{
return -1;
}
return s-len2;
}
時(shí)間復(fù)雜度:
對(duì)于Next函數(shù)近似接近O(m),KMP算法的時(shí)間復(fù)雜度為O(n),所以整個(gè)算法的時(shí)間復(fù)雜度為O(n+m)
空間復(fù)雜度:
多引入了O(m)的空間復(fù)雜度。
4.應(yīng)用KMP的一道面試題
給定兩個(gè)字符串是s1和s2,要判定s2是否能夠被s1做循環(huán)移位得到的字符串包含。例如s1=AABCD,s2 =CDAA,返回true,因?yàn)閟1循環(huán)移位可以變成CDAAB。給定s1=ACBD和s2=ACBD則返回false。
分析:不難發(fā)現(xiàn)對(duì)s2移位得到的字符串都將是字符串s1s1的子串,如果s2可以有s1循環(huán)移位得到,那么s2一定是s1s1的子串,這時(shí)KMP算法是不是就很管用了呢。
您可能感興趣的文章:
- C++ 數(shù)據(jù)結(jié)構(gòu)之kmp算法中的求Next()函數(shù)的算法
- java 中模式匹配算法-KMP算法實(shí)例詳解
- C語(yǔ)言中實(shí)現(xiàn)KMP算法的實(shí)例講解
- KMP算法精解及其Python版的代碼示例
- Python字符串匹配算法KMP實(shí)例
- JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(五):經(jīng)典KMP算法
- C語(yǔ)言kmp算法簡(jiǎn)單示例和實(shí)現(xiàn)原理探究
- KMP算法的C#實(shí)現(xiàn)方法
- 字符串的模式匹配詳解--BF算法與KMP算法
- KMP 算法實(shí)例詳解
相關(guān)文章
Visual?Studio下Eigen庫(kù)環(huán)境配置方式
這篇文章主要介紹了Visual?Studio下Eigen庫(kù)環(huán)境配置方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12C語(yǔ)言實(shí)現(xiàn)解析csv格式文件的示例代碼
CSV,有時(shí)也稱為字符分隔值,其文件以純文本形式存儲(chǔ)表格數(shù)據(jù)(數(shù)字和文本),本文為大家整理了C語(yǔ)言解析csv文件的方法,需要的可以參考一下2023-06-06