waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢(mèng)的舞臺(tái),心有多大,舞臺(tái)有多大。踏踏實(shí)實(shí)做事,認(rèn)認(rèn)真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評(píng)論 :: 0 Trackbacks
          轉(zhuǎn)自:http://www.aygfsteel.com/javacap/archive/2007/07/10/129405.html
          /**
           
          * Demonstrate KMP algorithm in Java
           
          *
           
          *
           
          */
          public class KMP {
              
              
              
          public static int indexOf(String target,String pattern)
              {
                  
          int pLen=pattern.length();
                  
          int tLen=target.length();
                  
                  
          //the fail function
                  int failFunc[]=new int[pLen];
                  
                  failFunc[
          0]=-1;
                  
                  
          //build fail function
                  for(int i=1;i<pLen;i++)
                  {
                      
          int j=failFunc[i-1];
                      
          while(pattern.charAt(i)!=pattern.charAt(j+1)&&j>=0)
                      {
                          
          //recursion 
                          j=failFunc[j];
                      }
                      
          if(pattern.charAt(i)==pattern.charAt(j+1))
                      {
                          failFunc[i]
          =j+1;
                      }
                      
          else 
                      {
                          failFunc[i]
          =-1;
                      }
                  }

                  
          int pPos=0,tPos=0;
                  
                  
          while(tPos<tLen&&pPos<pLen)
                  {
                      
          if(target.charAt(tPos)==pattern.charAt(pPos))
                      {
                          
          //match ,then do forward
                          tPos++;
                          pPos
          ++;
                      }
                      
          else if(pPos==0)
                      {
                          
          //target go forward
                          tPos++;
                      }
                      
          else
                      {
                          
          //target postion don't change,pattern go back  
                          pPos=failFunc[pPos-1]+1;
                      }
                  }
                  
                  
          if(pPos<pLen)return -1;
                  
          else return tPos-pLen;
                  
                  
                  
              }

          }

          posted on 2009-04-15 22:27 weesun一米陽光 閱讀(439) 評(píng)論(0)  編輯  收藏 所屬分類: JAVA源碼總結(jié)備用
          主站蜘蛛池模板: 漠河县| 沙雅县| 桂林市| 迭部县| 山西省| 泾源县| 桃江县| 旅游| 康定县| 分宜县| 天柱县| 和顺县| 平乡县| 政和县| 治县。| 大邑县| 凌云县| 开平市| 阆中市| 沐川县| 阳谷县| 冕宁县| 隆回县| 肇源县| 张北县| 射洪县| 中牟县| 永寿县| 衡山县| 南皮县| 鱼台县| 和平区| 于都县| 玛沁县| 枣强县| 安丘市| 项城市| 屏东县| 邯郸市| 综艺| 鸡泽县|