waysun一路陽光

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

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          轉自: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一米陽光 閱讀(432) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 固始县| 边坝县| 香港 | 偃师市| 通海县| 和平区| 濉溪县| 雷州市| 汝城县| 宁远县| 宿松县| 长兴县| 集安市| 酉阳| 淄博市| 浦江县| 楚雄市| 孟州市| 清苑县| 孝昌县| 贵德县| 乳山市| 六盘水市| 丰原市| 商城县| 通江县| 河北省| 枞阳县| 屏南县| 田阳县| 九寨沟县| 德格县| 儋州市| 甘肃省| 六枝特区| 黔西| 从化市| 石狮市| 右玉县| 千阳县| 常宁市|