<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                轉載請注明出處 http://blog.csdn.net/pony_maggie/article/details/37832707 作者:小馬 在一個長串中查找一個子串是較常用的操作。各種信息檢索系統,文字處理系統都少不了。本文介紹一個非常著名的KMP模式匹配算法用于子串查找。 先拋開KMP,正常情況一下我們會如何設計這個邏輯。一個主串S, 要在里面查找一個子串T,如果找到了返回T在S中開始的位置,否則返回-1。應該不難,需要一個輔助函數,從一個串口的指定位置,取出指定長度的子串。思想是這樣: 在主串S中從開始位置,取長度和T相等的子串比羅,若相等,返回該位置的索引值,否則位置增加1, 繼續上面的過程。代碼很簡單,如下: ~~~ //普通方法查找子串 //在主串s中查找t, 若找到匹配,返回索引位置(從0到len-1) //否則返回-1 int IndexOfString(char* srcString, char* keyString) { int nSrcLen = 0; int nKeyString = 0; int i = 0; char szTemp[1024] = {0};//假設足夠大 if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyString = strlen(keyString); if (nKeyString > nSrcLen) { return -1; } while(i < (nSrcLen-nKeyString)) { memset(szTemp, 0x00, sizeof(szTemp)); SubString(srcString, szTemp, i, nKeyString); if (memcmp(szTemp, keyString, nKeyString) != 0) { i++; } else return i; } return -1; } ~~~ 再進一步,把輔助函數去掉,通過頻繁操作下標也同樣可以實現,思想跟上面查不多,只不過換成一個個字符比較,代碼如下: ~~~ int IndexOfString1(char* srcString, char* keyString) { int nSrcLen = 0; int nKeyLen = 0; int i = 0; int j = 0; char szTemp[1024] = {0};//假設足夠大 if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyLen = strlen(keyString); if (nKeyLen > nSrcLen) { return -1; } while((i < nSrcLen) && (j <nKeyLen)) { if (srcString[i] == keyString[j]) { i++; j++; } else { i = i - j + 1;//主串回退到下一個位置 j = 0; //子串重新開始 } } if (j >= nKeyLen) { return (i - nKeyLen);//找到 } return -1; } ~~~ 分析一下上面算法的時間復雜度(兩個算法其實是一樣的)。舉個例子,主串是: “A STRING SEARCHING EXAMPLE CONSISTINGOF SIMPLE TEXT” 子串是 “STING” 用上面的算法,會發現除了上面標記紅色的字符比較了兩次,其它都是比較一次,如果主串的長度是m, 子串的長度是n, 時間復雜度基本是O(m+n)。好像不錯,效率挺高。再來看一個。主串是: “000000000000000000000000000000000000000000000000000000000001” 子串是 “00000001” 在腦海里想像一下這個過程,很容易得出它的時間復雜度是O(m*n)。所以這種類似窮舉的查找子串算法,時間復雜度與主串和子串的內容有很大關系,復雜度不固定。而且像上面那樣的01串在計算機處理中還比較常見,所以需要更好的算法。 KMP(三個發明人的名字首字母)算法可以保證不論哪種情況都可以在O(m+n)的時間復雜度內完成匹配。它改進的地方是當出現比較不等時,主串中位置不回退,而是利用已經匹配的結果,將子串向右滑動盡可能遠的距離后,再繼續比較,看個例子: ![](https://box.kancloud.cn/2016-06-13_575e9295265c7.jpg) 在第三趟匹配中,當i=12, j=7時,字符不相等,這時不用回退到i=7,j=1重新比較,而是i不變,j變成next[j]的值就行了,上圖中是3, 也就是圖中第四趟的比較位置。 這個確實很強大,現在要解決的問題是next[j]如何計算。其實這個推導也不難,很多算法的書上都有詳細的過程,我這里就不贅述了。只把結果給出來: 1 當j = 0時,next[j] =-1。 2 當j =1時,next[j] = 0。 3 滿足1 < k < j,且p[0…k-1] =p[j-k…j-1]的最大的k, next[j] = k。 4 其它情況,next[j] = 0。 根據上面的邏輯,很容易寫出一個計算next的函數,如下: ~~~ static void getNext(char* strSub) { int j, k, temp; int nLen = 0; j = k = temp = 0; nLen = strlen(strSub); memset(g_next, 0x00, sizeof(g_next));//每次進來都清空 for (j = 0; j < nLen; j++) { if (j == 0) { g_next[j] = -1; } else if (j == 1) { g_next[j] = 0; } else //取集合不為空時的最大值 { temp = j - 1; for (k = temp; k > 0; k--) { if (isEqual(strSub, j, k)) { g_next[j] = k; break; } } if (k == 0)//集合為空 { g_next[j] = 0; } } } } ~~~ 得到next之后,整個過程如下: 以指針i和j分別表示主串和子串中正在比較的字符,若Si = Pj, 則i和j都增1,繼續下一個字符的比較。否則i不變,j退到next[j]的位置再比較,若相等,再各自增1,否則j再退到next[j]。循環進行,如果中間遇到next[j]為-1的情況,此時主串要增1,子串j變為0,表示要從主串的下一個位置重新開始比較。 把上面的過程轉化為代碼: ~~~ //KMP算法查找子串 //在主串s中查找t, 若找到匹配,返回索引位置(從0到len-1) //否則返回-1 int IndexOfStringKMP(char* srcString, char* keyString) { int i = 0; int j = 0; int nSrcLen = 0; int nKeyLen = 0; if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyLen = strlen(keyString); if (nKeyLen > nSrcLen) { return -1; } getNext(keyString);//先計算next值 while ((i < nSrcLen) && (j < nKeyLen)) { if ((srcString[i] == keyString[j]) || (j == -1)) { i++; j++; } else { j = g_next[j]; } } if (j >= nKeyLen) { return (i - nKeyLen);//找到 } return -1; } ~~~ 代碼下載地址: http://download.csdn.net/detail/pony_maggie/7630329 或 https://github.com/pony-maggie/StringIndex
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看