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é)備用 
	
          

          







          
	    
    




          








          

				

          




    







          
        
	




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