kmp算法

void getnext(const char P[], int next[])
{
    int q, k;
    int m = strlen(P); // 模板字符串的長度
    next[0] = 0;
    for(q = 1, k = 0; q < m; ++q) { // 從第二個字符開始轧铁，依次計算每個字符對應(yīng)的next值
        while(k > 0 && P[q] != P[k]) {
            k = next[k-1];
        }
        if(P[q] == P[k]) {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char T[], const char P[], int next[]) 
{
    int n, m;
    int i, q;
    n = strlen(T);
    m = strlen(P);
    getnext(P, next); // 計算next數(shù)組
    for(i = 0, q = 0; i < n; ++i) {
        while(q > 0 && P[q] != T[i]) {
            q = next[q-1];
        }
        if(P[q] == T[i]) q++;
        if(q == m) {
            // 輸出找到的位置
            cout << (i-m+1) << endl;
        }
    }
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市飞苇，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌，老刑警劉巖飞几，帶你破解...
沈念sama閱讀 211,123評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異独撇，居然都是意外死亡屑墨，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,031評論 2贊 384
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門纷铣，熙熙樓的掌柜王于貴愁眉苦臉地迎上來卵史，“玉大人，你說我怎么就攤上這事关炼〕谈梗” “怎么了？”我有些...
開封第一講書人閱讀 156,723評論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵儒拂，是天一觀的道長寸潦。經(jīng)常有香客問我，道長社痛，這世上最難降的妖魔是什么见转？我笑而不...
開封第一講書人閱讀 56,357評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮蒜哀，結(jié)果婚禮上斩箫，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好乘客，可當(dāng)我...
茶點(diǎn)故事閱讀 65,412評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布狐血。她就那樣靜靜地躺著，像睡著了一般易核。火紅的嫁衣襯著肌膚如雪匈织。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,760評論 1贊 289
城市分裂傳說
那天牡直，我揣著相機(jī)與錄音缀匕，去河邊找鬼。笑死碰逸，一個胖子當(dāng)著我的面吹牛乡小，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播饵史，決...
沈念sama閱讀 38,904評論 3贊 405
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼满钟，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了约急？” 一聲冷哼從身側(cè)響起零远，我...
開封第一講書人閱讀 37,672評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤苗分，失蹤者是張志新（化名）和其女友劉穎厌蔽，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體摔癣，經(jīng)...
沈念sama閱讀 44,118評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡奴饮，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,456評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了择浊。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片戴卜。...
茶點(diǎn)故事閱讀 38,599評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖琢岩，靈堂內(nèi)的尸體忽然破棺而出投剥，到底是詐尸還是另有隱情，我是刑警寧澤担孔，帶...
沈念sama閱讀 34,264評論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布江锨，位于F島的核電站，受9級特大地震影響糕篇，放射性物質(zhì)發(fā)生泄漏啄育。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,857評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一拌消、第九天我趴在偏房一處隱蔽的房頂上張望挑豌。院中可真熱鬧，春花似錦、人聲如沸氓英。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,731評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽铝阐。三九已至壳鹤，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間饰迹，已是汗流浹背芳誓。一陣腳步聲響...
開封第一講書人閱讀 31,956評論 1贊 264
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留啊鸭，地道東北人锹淌。一個月前我還...
沈念sama閱讀 46,286評論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長得像赠制，于是被迫代替她去往敵國和親赂摆。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,465評論 2贊 348

kmp算法

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