waysun一路陽光

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

            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 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一米陽光 閱讀(431) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結(jié)備用
          主站蜘蛛池模板: 石屏县| 南靖县| 牙克石市| 宁乡县| 邢台市| 渝中区| 鸡泽县| 平谷区| 万荣县| 塔城市| 房山区| 云安县| 日照市| 西城区| 台湾省| 喜德县| 赣州市| 海淀区| 林州市| 南涧| 旌德县| 镇远县| 太仆寺旗| 马尔康县| 宣武区| 西城区| 威海市| 赤水市| 丰宁| 平定县| 安新县| 左云县| 和田县| 寿阳县| 东光县| 凯里市| 桓台县| 阿克苏市| 金堂县| 永吉县| 阿拉尔市|