waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks

          背景簡介:KMP算法用來處理字符串匹配的。給你A,B兩個字符串,檢查B串是否是A串的子串,類似于Java的String.indexOf("")。之所以叫做KMP,是因為這個算法是由Knuth、Morris、Pratt三個提出來的,取了這三個人的名字的頭一個字母。

          原理介紹:找到匹配失敗時的最合適的回退位置,而不是簡單的回退到子串的第一個字符(常規的枚舉查找方式,是簡單的回退到子串的第一個字符,接下來準備寫一篇KMP算法的性能分析Java實現實例),即可提高查找的效率。因此為了找到這個合適的位置,先對子串預處理,從而得到一個回退位置的數組。過多的理論就不介紹了。

          總體而言比較簡單,KMP算一個經典的算法例子,很多筆試、面試也會問起。現總結一下,放在這里供大家參考、交流,希望對大家有所幫助,下面直接給出實現例子,測試與分析也包含其中。

          一、一個文件源代碼

          KMP.java

          源代碼為:

          package algorithm.kmp;

          /**
          * KMP算法的Java實現例子與測試、分析
          * @author 崔衛兵
          * @date 2009-3-25
          */
          public class KMP {
          /**
          * 對子串加以預處理,從而找到匹配失敗時子串回退的位置
          * 找到匹配失敗時的最合適的回退位置,而不是回退到子串的第一個字符,即可提高查找的效率
          * 因此為了找到這個合適的位置,先對子串預處理,從而得到一個回退位置的數組
          * @param B,待查找子串的char數組
          * @return
          */
          public static int[] preProcess(char [] B) {
          int size = B.length;
          int[] P = new int[size];
          P[0]=0;
          int j=0;
          //每循環一次,就會找到一個回退位置
          for(int i=1;i
          //當找到第一個匹配的字符時,即j>0時才會執行這個循環
          //或者說p2中的j++會在p1之前執行(限于第一次執行的條件下)
          //p1
          while(j>0 %26amp;%26amp; B[j]!=B[i]){
          j=P[j];
          }
          //p2,由此可以看出,只有當子串中含有重復字符時,回退的位置才會被優化
          if(B[j]==B[i]){
          j++;
          }
          //找到一個回退位置j,把其放入P[i]中
          P[i]=j;
          }
          return P;
          }

          /**
          * KMP實現
          * @param parStr
          * @param subStr
          * @return
          */
          public static void kmp(String parStr, String subStr) {
          int subSize = subStr.length();
          int parSize = parStr.length();
          char[] B = subStr.toCharArray();
          char[] A = parStr.toCharArray();
          int[] P = preProcess(B);
          int j=0;
          int k =0;
          for(int i=0;i
          //當找到第一個匹配的字符時,即j>0時才會執行這個循環
          //或者說p2中的j++會在p1之前執行(限于第一次執行的條件下)
          //p1
          while(j>0 %26amp;%26amp; B[j]!=A[i]){
          //找到合適的回退位置
          j=P[j-1];
          }
          //p2 找到一個匹配的字符
          if(B[j]==A[i]){
          j++;
          }
          //輸出匹配結果,并且讓比較繼續下去
          if(j==subSize){
          j=P[j-1];
          k++;
          System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
          }
          }
          System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
          }

          public static void main(String[] args) {
          //回退位置數組為P[0, 0, 0, 0, 0, 0]
          kmp("abcdeg, abcdeh, abcdef!這個會匹配1次","abcdef");
          //回退位置數組為P[0, 0, 1, 2, 3, 4]
          kmp("Test ititi ititit! Test ititit!這個會匹配2次","ititit");
          //回退位置數組為P[0, 0, 0]
          kmp("測試漢字的匹配,崔衛兵。這個會匹配1次","崔衛兵");
          //回退位置數組為P[0, 0, 0, 1, 2, 3, 4, 5, 6]
          kmp("這個會匹配0次","it1it1it1");
          }
          }

          二、輸出結果

          Find subString 'abcdef' at 16
          Totally found 1 times for 'abcdef'.

          Find subString 'ititit' at 11
          Find subString 'ititit' at 24
          Totally found 2 times for 'ititit'.

          Find subString '崔衛兵' at 8
          Totally found 1 times for '崔衛兵'.

          Totally found 0 times for 'it1it1it1'.

          三、總結

          總體而言,KMP算法通過找到合適的回退位置從而可以提高匹配效率,但是如果匹配位置都是第一個字符呢?例如測試代碼中的

          //回退位置數組為P[0, 0, 0, 0, 0, 0]
          kmp("abcdeg, abcdeh, abcdef!這個會匹配2次","abcdef");

          接下來準備寫一篇KMP算法的性能分析Java實現實例,下文再見。^_^


          posted on 2009-04-15 22:56 weesun一米陽光 閱讀(318) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 宁波市| 屏山县| 甘南县| 扬中市| 白山市| 五大连池市| 常山县| 昌邑市| 偃师市| 平原县| 胶南市| 横峰县| 克山县| 静宁县| 武宣县| 营山县| 阜南县| 临漳县| 马龙县| 莆田市| 高陵县| 长白| 潮安县| 宽甸| 丽水市| 无棣县| 桦川县| 留坝县| 泽州县| 穆棱市| 咸宁市| 习水县| 乌兰浩特市| 合江县| 遵义市| 洪雅县| 大埔县| 江陵县| 天柱县| 武鸣县| 桐柏县|