waysun一路阳光

不轻易服输,不轻言放弃.--心是梦的舞台,心有多大,舞台有多大。踏踏实实做事,认认真真做人。

  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  167 随笔 :: 1 文章 :: 64 评论 :: 0 Trackbacks
转自:http://www.blogjava.net/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一米阳光 阅读(393) 评论(0)  编辑  收藏 所属分类: JAVA源码总结备用

只有注册用户登录后才能发表评论。


网站导航: