首页 > 其他 > 详细

KMP字符串匹配

时间:2018-03-16 18:22:07      阅读:221      评论:0      收藏:0      [点我收藏+]

http://blog.csdn.net/starstar1992/article/details/54913261

public class Test{
    public static void main(String[] args){ 
        String s1="abababd";
        String s2="abd";
        System.out.println(kmp(s1,s2));
    }  
    public static void getNext(String s,int[] next){
        int len=s.length();
        next[0]=-1;
        int k=-1;
        for(int i=1;i<len;i++){
            while(k!=-1 && s.charAt(k+1)!=s.charAt(i)){
                k=next[k];
            }
            if(s.charAt(k+1)!=s.charAt(i)){
                k++;
            }
            next[i]=k;
        }
    }
    public static int kmp(String str,String subStr){
        int[] next=new int[subStr.length()];
        getNext(subStr,next);
        int k=-1;
        int len=str.length();
        for(int i=0;i<len;i++){
            while(k!=-1 && str.charAt(i)!=subStr.charAt(k+1)){
                k=next[k];
            }
            if(str.charAt(i)==subStr.charAt(k+1)){
                    k++;
            }
            if(k==subStr.length()-1){
                return i-subStr.length()+1;
            }
        }
        return -1;
    }
}

 

KMP字符串匹配

原文:https://www.cnblogs.com/xinyi-blog/p/8583644.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!