waysun一路阳光

不轻易服输,不轻言放弃.--心是梦的舞台，心有多大，舞台有多大。踏踏实实做事，认认真真做人。
  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  167 随笔 :: 1 文章 :: 64 评论 :: 0 Trackbacks
KMP算法JAVA实现【转】
转自：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一米阳光 阅读(392) 评论(0)  编辑  收藏 所属分类: JAVA源码 、总结备用

只有注册用户登录后才能发表评论。
网站导航: