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é)備用
          主站蜘蛛池模板: 周口市| 肥西县| 万州区| 天祝| 曲靖市| 墨竹工卡县| 阜新| 日照市| 咸阳市| 正定县| 广饶县| 晋宁县| 布拖县| 鸡泽县| 红桥区| 新闻| 静乐县| 克什克腾旗| 比如县| 黔江区| 浙江省| 镇巴县| 防城港市| 永城市| 西丰县| 夹江县| 福建省| 梨树县| 合山市| 巴彦淖尔市| 台中县| 新干县| 舟曲县| 吉安市| 隆安县| 荥经县| 沐川县| 息烽县| 南木林县| 南漳县| 宜春市|