字符串的模式匹配(BF算法與KMF算法)

串的模式匹配

1.樸素的模式匹配(Brute-Force)算法

假設(shè)待匹配的目標(biāo)串是adbcade,而模式串是ade究抓,那么匹配的時候是按:
    a--d--b-->不匹配;
    d-->不匹配;   //注意這里在上一個發(fā)現(xiàn)不匹配時弛随,是從上一個匹配開始的下一個位置開始重新匹配的。

Brute-Force算法的實現(xiàn):

public int indexOf(String target,String pattern){
        //判斷目標(biāo)串,匹配串是否滿足條件巍沙。
        if(pattern != null && target != null && target.length() >= pattern.length()){
            //start指開始匹配的字符起始位置
            int start = 0;
            //count指匹配到的字符數(shù)目
            int count = 0;
            //當(dāng)目標(biāo)串剩余未匹配的長度大于或等于匹配串串長度犯祠,循環(huán)繼續(xù)
            while(target.length() - start >= pattern.length()){
                //滿足條件
                if(target.charAt(count + start) == pattern.charAt(count)){              
                    //匹配一個字符后加一。
                    count ++;
                }else{
                        //不滿足匹配窖铡,count置零疗锐,起始匹配位置加一。
                    count = 0;
                    start ++;
                }
                //若count==pattern费彼,說明已經(jīng)完成了一次匹配滑臊。
                if(count == pattern.length()){
                    return start;
                }
            }
        }
        //匹配失敗返回-1
        return -1;
    }

測試程序以及運行結(jié)果:

public static void main(String[] args) {
        // TODO Auto-generated method stub
        String target = "adbcade";
        String pattern = "ade";
        BruteForceStringPattern sfsp = new BruteForceStringPattern();
        System.out.println(sfsp.indexOf(target, pattern));
    }
    
    4
Brute-Force算法易于理解,但是時間效率不高箍铲。它是一種帶回溯的模式匹配算法雇卷,將目標(biāo)串中所有長度為匹配串長度的字串依次與匹配串比較。

雖然沒有任何丟失可能匹配字符的可能,但是每次的匹配沒有用到前一次匹配的比較結(jié)果关划,比較多次重復(fù)膘融,降低了算法效率。
時間復(fù)雜度:
m = pattern.length();
n = target.length();
最好的情況:O(m) (一次比較成功)
最壞的情況:O(n(n-m+1)m) 一般n>>m祭玉,所以O(shè)(nm) (比較到最后一次才成功)

2.無回溯的模式匹配(KMP)算法

先來一波kmp算法的百科介紹:

KMP算法是一種改進的字符串匹配算法氧映,由D.E.Knuth,J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)
脱货,因此人們稱它為克努特——莫里斯——普拉特操作(簡稱KMP算法)岛都。
KMP算法的關(guān)鍵是利用匹配失敗后的信息,盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的振峻。
具體實現(xiàn)就是實現(xiàn)一個next()函數(shù)臼疫,函數(shù)本身包含了模式串的局部匹配信息。

無回溯的模式匹配算法首先目標(biāo)串的祛除了目標(biāo)串的回溯扣孟,其次烫堤,通過getNext()算法,匹配串也做到了部分不回溯凤价。

無回溯算法的核心是如何實現(xiàn)這個next()算法:

    public int[] next(String pattern){
        int i = -1;
        int j = 0;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while(j < pattern.length() - 1){
            if(i == -1 || pattern.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
                next[j] = i;
            }else{
                i = -1;
            }
        }
        return next;
    }

實際上next()算法就是來 判斷pattern的子字符串與當(dāng)pattern的0位置開始的字符串是否相同鸽斟,第一個next[0]默認(rèn)為1,接下來的如果不相同next[i]為0利诺,如果第一個相同富蓄,為0,若連續(xù)開始相同,則依次++1
如:

aaaaaaa的next():
[-1,0,1,2,3,4,5]

abab的next():
[-1,0,0,1]

如果pattern的首字符在pattern剩余的字符串里沒有再出現(xiàn)過慢逾,那么getNext()獲取的next[]必然是[-1,0,...,0]這樣的立倍。

匹配方法如下:

public int kmp(String target,String pattern){
        if(target != null && pattern != null && target.length() > pattern.length()){
            int start = 0;
            int[] next = next(pattern);
            int count = next[start];
            while(target.length() - start + count >= pattern.length()){
                if(count == -1 || target.charAt(start) == pattern.charAt(count)){
                    count ++;
                    start ++;
                }else{
                    //這里就是核心了,如果next[count] <= 0 目標(biāo)字符串直接從當(dāng)前的下一個開始比較侣滩。
                    //因為等于-1的話說明是在匹配第一個字符串口注,當(dāng)前匹配失敗,不可能再與pattern第一個字符匹配了君珠,當(dāng)然是要繼續(xù)匹配下一個寝志,如果是0的話,說明是在匹配第一個與pattern頭相同的串或者匹配與pattern頭無關(guān)的字符葛躏,匹配失敗澈段,當(dāng)然也是繼續(xù)匹配下一個字符串。
                    count = next[count];
                }
                
                if(count == pattern.length()){
                    return start - count;
                }
            }
        }
        return -1;
    }

kmp算法的最壞的比較次數(shù)是m+n舰攒,next算法的時間復(fù)雜度是0(m),kmp比較是O(n),與BF算法相比悔醋,已經(jīng)大大縮小了比較的時間摩窃。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子猾愿,更是在濱河造成了極大的恐慌鹦聪,老刑警劉巖,帶你破解...
    沈念sama閱讀 212,657評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蒂秘,死亡現(xiàn)場離奇詭異泽本,居然都是意外死亡,警方通過查閱死者的電腦和手機姻僧,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,662評論 3 385
  • 文/潘曉璐 我一進店門规丽,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人撇贺,你說我怎么就攤上這事赌莺。” “怎么了松嘶?”我有些...
    開封第一講書人閱讀 158,143評論 0 348
  • 文/不壞的土叔 我叫張陵艘狭,是天一觀的道長。 經(jīng)常有香客問我翠订,道長巢音,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,732評論 1 284
  • 正文 為了忘掉前任尽超,我火速辦了婚禮港谊,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘橙弱。我一直安慰自己歧寺,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 65,837評論 6 386
  • 文/花漫 我一把揭開白布棘脐。 她就那樣靜靜地躺著斜筐,像睡著了一般。 火紅的嫁衣襯著肌膚如雪蛀缝。 梳的紋絲不亂的頭發(fā)上顷链,一...
    開封第一講書人閱讀 50,036評論 1 291
  • 那天,我揣著相機與錄音屈梁,去河邊找鬼嗤练。 笑死,一個胖子當(dāng)著我的面吹牛在讶,可吹牛的內(nèi)容都是我干的煞抬。 我是一名探鬼主播,決...
    沈念sama閱讀 39,126評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼构哺,長吁一口氣:“原來是場噩夢啊……” “哼革答!你這毒婦竟也來了战坤?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,868評論 0 268
  • 序言:老撾萬榮一對情侶失蹤残拐,失蹤者是張志新(化名)和其女友劉穎途茫,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體溪食,經(jīng)...
    沈念sama閱讀 44,315評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡囊卜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,641評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了错沃。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片栅组。...
    茶點故事閱讀 38,773評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖捎废,靈堂內(nèi)的尸體忽然破棺而出笑窜,到底是詐尸還是另有隱情,我是刑警寧澤登疗,帶...
    沈念sama閱讀 34,470評論 4 333
  • 正文 年R本政府宣布排截,位于F島的核電站,受9級特大地震影響辐益,放射性物質(zhì)發(fā)生泄漏断傲。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 40,126評論 3 317
  • 文/蒙蒙 一智政、第九天 我趴在偏房一處隱蔽的房頂上張望认罩。 院中可真熱鬧,春花似錦续捂、人聲如沸垦垂。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,859評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽劫拗。三九已至,卻和暖如春矾克,著一層夾襖步出監(jiān)牢的瞬間页慷,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,095評論 1 267
  • 我被黑心中介騙來泰國打工胁附, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留酒繁,地道東北人。 一個月前我還...
    沈念sama閱讀 46,584評論 2 362
  • 正文 我出身青樓控妻,卻偏偏與公主長得像州袒,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子饼暑,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,676評論 2 351

推薦閱讀更多精彩內(nèi)容