KMP算法代碼實(shí)現(xiàn)

先上代碼

int  getNextArray(char a[], int n, int *p)
{
   if(NULL == a || 0 == n)
   {
      return -1;
   }

   p[0] = -1;
   p[1] = 0;
   int pos = 2;
   int ch = 0;

   while(pos < n)
   {
     if(a[pos] == a[ch])
     {
         p[pos] = p[pos - 1] + 1;
         pos ++;
         ch ++;

     }
     else if(0 != ch)
     {
       ch = p[ch];
     }
     else
     {
       p[pos] = 0;
       pos ++;
     }

   }

   return 0;

}

int matchIndex(char dest[],int destLen, char match[], int matchLen)
{
   if(NULL == dest || NULL == match || destLen < matchLen)
   {
     return -1;
   }

   int nextArray[N]={0};
   int nError = getNextArray(match,  matchLen, nextArray);
   if(0 != nError)
   {
     return -1;
   }

   int dIndex = 0;
   int mIndex = 0;
   while(dIndex < destLen && mIndex < matchLen)
   {
     if(dest[dIndex] == match[mIndex])
     {
        dIndex ++ ;
        mIndex++;
     }
     else
     {

        if(mIndex < 2)
        {
            dIndex ++;
            mIndex = 0;
        }
        else
        {
            mIndex = nextArray[mIndex-1] ;
        }
     }

    }

   if(mIndex == matchLen)
   {
      return dIndex - matchLen + 1;
   }
   else
   {
      return -2;
   }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子照捡,更是在濱河造成了極大的恐慌,老刑警劉巖吃引,帶你破解...
    沈念sama閱讀 212,542評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異刽锤,居然都是意外死亡镊尺,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,596評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門姑蓝,熙熙樓的掌柜王于貴愁眉苦臉地迎上來鹅心,“玉大人,你說我怎么就攤上這事纺荧。” “怎么了?”我有些...
    開封第一講書人閱讀 158,021評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵宙暇,是天一觀的道長输枯。 經(jīng)常有香客問我,道長占贫,這世上最難降的妖魔是什么桃熄? 我笑而不...
    開封第一講書人閱讀 56,682評(píng)論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮型奥,結(jié)果婚禮上瞳收,老公的妹妹穿的比我還像新娘。我一直安慰自己厢汹,他們只是感情好螟深,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,792評(píng)論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著烫葬,像睡著了一般界弧。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上搭综,一...
    開封第一講書人閱讀 49,985評(píng)論 1 291
  • 那天垢箕,我揣著相機(jī)與錄音,去河邊找鬼兑巾。 笑死条获,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的蒋歌。 我是一名探鬼主播月匣,決...
    沈念sama閱讀 39,107評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼奋姿!你這毒婦竟也來了锄开?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,845評(píng)論 0 268
  • 序言:老撾萬榮一對情侶失蹤称诗,失蹤者是張志新(化名)和其女友劉穎萍悴,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體寓免,經(jīng)...
    沈念sama閱讀 44,299評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡癣诱,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,612評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了袜香。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片撕予。...
    茶點(diǎn)故事閱讀 38,747評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖蜈首,靈堂內(nèi)的尸體忽然破棺而出实抡,到底是詐尸還是另有隱情欠母,我是刑警寧澤,帶...
    沈念sama閱讀 34,441評(píng)論 4 333
  • 正文 年R本政府宣布吆寨,位于F島的核電站赏淌,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏啄清。R本人自食惡果不足惜六水,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,072評(píng)論 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望辣卒。 院中可真熱鬧掷贾,春花似錦、人聲如沸荣茫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,828評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽计露。三九已至博脑,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間票罐,已是汗流浹背叉趣。 一陣腳步聲響...
    開封第一講書人閱讀 32,069評(píng)論 1 267
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留该押,地道東北人疗杉。 一個(gè)月前我還...
    沈念sama閱讀 46,545評(píng)論 2 362
  • 正文 我出身青樓,卻偏偏與公主長得像蚕礼,于是被迫代替她去往敵國和親烟具。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,658評(píng)論 2 350

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