国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C > 正文

快速模式匹配算法(KMP)的深入理解

2020-01-26 16:04:22
字體:
來源:轉載
供稿:網友
恐怕現在用過電腦的人,一定都知道大部分帶文本編輯功能的軟件都有一個快捷鍵ctrl+f 吧(比如word)。這個功能主要來完成“查找”,“替換”和“全部替換”功能的,其實這就是典型的模式匹配的應用,即在文本文件中查找串。

1.模式匹配
模式匹配的模型大概是這樣的:給定兩個字符串變量S和P,其中S成為目標串,其中包含n個字符,P稱為模式串,包含m個字符,其中m<=n。從S的給定位置(通常是S的第一個位置)開始搜索模式P。如果找到,則返回模式P在目標串中的位置(即:P的第一個字符在S中的下標)。如果在目標串S中沒有找到模式串P,則返回-1.這就是模式匹配的定義啦,下面來看看怎么實現模式匹配算法吧。

2.樸素的模式匹配
樸素的模式匹配算法非常簡單,容易理解,大概思路是這樣的:從S的第一個字符S0開始,將P中的字符依次和S中字符比較,若S0=P0 && …… && Sm-1 = Pm-1,則證明匹配成功,剩下的匹配無需進行了,返回下標0。若在某一步Si != Pi 則P中剩下的字符也不用比較了,不可能匹配成功了,然后從S中第二個字符開始與P中第一個字符進行比較,同理,也是知道Sm = Pm-1或者找到某個i使得Si != S-1為止。依次類推若知道以S中第n-m個開始字符為止,還沒有匹配成功則證明S中不存模式P。(想想為什么這里強調是n-m)這個代碼實現應該是非常簡單的,具體開始參考strstr函數的內部實現。可以看看百度百科,給個鏈接http://baike.baidu.com/view/745156.htm,這里不寫出來了,還得趕緊進入正題KMP呢。

3.快速模式匹配算法(KMP)
樸素的模式匹配效率不高的主要原因是進行了重復的字符比較。下一次比較和上一次比較沒有任何的聯系,是樸素模式匹配的缺點,其實上一次比較的比較結果是可以利用的,這就產生了快速模式匹配。在樸素的模式匹配中,目標串S的下標移動是一步一步的,這其實并不好,移動步數沒有必要為1。
現在不妨假設,當前匹配情況是這樣的:S0 …… St St+1 …… St+j  與 P0 P1…… Pj ,現在正在嘗試匹配的字符是St+j+1和Pj+1,并且St+j+1 != Pj+1,言外之意就是說St St+1……St+j和P0 P1……Pj是完全匹配的。那么這個時候,S中下一次匹配開始位置應該是什么呢??按照樸素的模式匹配,下次比較應該從St+1開始,并且令St+1和P0比較,但是在快速模式匹配中并不是這樣,快速模式匹配選擇St+j+1和Pk+1比較,K是什么呢?K是這樣的一個值,使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配,不妨設k=next[j],因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要進行匹配的兩個字符應為St+j+1和Pk+1。S和P都沒有回溯到下標0在進行比較,這就是KMP之所以快的原因啦。
現在關鍵問題來了,這個K怎么能得到呢?如果得到這個K值復雜度高,那這個思路就不好了,其實這個K呢,只和模式串P有關系,并且要求m個k,k = next[j],因此只要算一次存儲到next數組中就可以了,并且時間復雜度和m有關系(線性關系)。看看具體怎么求next數組的值,即求k。
用歸納法求next[]:設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。也就是說h = next(k);看出來了吧,這是個迭代的過程。(也就是以前的結果對求以后的值有用)
(2)如果不存這樣的h,說明P0 P1……Pj+1中沒有前后相等的子串,因此next[j+1] =-1.
(3)如果存在這樣的h,繼續檢驗Ph和Pj是否相等。知道找到這中相等的情況,或者確定為-1求next[j+1]的過程結束。
看看實現的代碼:
復制代碼 代碼如下:

View Code
int next[20] ={0};
//注意返回結果是一個數組next,保存m個k值得地方,即若next[j]=k
//則str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
//這樣當des[t+j+1]和pat[j+1]匹配失敗時,下一個匹配位置為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)//迭代的過程
        {
            i = next[i];
        }
        if(str[j] == str[i+1])
        {
            next[j] = i+1;
        }
        else
        {
            next[j] = -1;
        }
    }
}

現在有了next數組保存的k值,就可以實現KMP算法了:
復制代碼 代碼如下:

View Code
//des是目標串,pat是模式串,len1和len2是串的長度
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++;//若第一個字符就匹配失敗,則從des的下一個字符開始
            }
            else
            {
                p = next[p-1]+1;//用失敗函數確定pat應回溯到的字符
            }
        }
    }
    if(p < len2)//整個過程匹配失敗
    {
        return -1;
    }
    return s-len2;
}

時間復雜度:
對于Next函數近似接近O(m),KMP算法的時間復雜度為O(n),所以整個算法的時間復雜度為O(n+m)
空間復雜度:
多引入了O(m)的空間復雜度。
4.應用KMP的一道面試題
給定兩個字符串是s1和s2,要判定s2是否能夠被s1做循環移位得到的字符串包含。例如s1=AABCD,s2 =CDAA,返回true,因為s1循環移位可以變成CDAAB。給定s1=ACBD和s2=ACBD則返回false。
分析:不難發現對s2移位得到的字符串都將是字符串s1s1的子串,如果s2可以有s1循環移位得到,那么s2一定是s1s1的子串,這時KMP算法是不是就很管用了呢。
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表

圖片精選

主站蜘蛛池模板: 富裕县| 自贡市| 辽宁省| 兴和县| 宜兴市| 达日县| 江口县| 林西县| 五华县| 辛集市| 徐水县| 铜山县| 喀喇沁旗| 西藏| 工布江达县| 炎陵县| 西乡县| 梅州市| 当涂县| 白银市| 米易县| 屏东县| 余干县| 漠河县| 资中县| 庄河市| 迁西县| 曲周县| 襄汾县| 宁国市| 苍山县| 巨野县| 太谷县| 锡林浩特市| 柳江县| 温泉县| 孟州市| 孟州市| 射洪县| 酉阳| 东乌|