KMP字符串匹配算法

太久没写算法,KMP都忘了。。。

 

class Solution {
    public int strStr(String s, String p) {
        //s是父串,p是子串
        int[] next = new int[p.length()];
        //构建next
        int i =1,now =0;
        while(i<p.length()){
            if(p.charAt(i)==p.charAt(now)){
                now++;
                next[i] = now;
                i++;
            }else if(now!=0){
                now = next[now-1];
            }else{
                next[i] = now;
                i++;
            }
        }
        System.out.print("next: ");
        for (int j = 0; j < next.length; j++) {
            System.out.print(next[j]+" ");
        }
        System.out.println(" ");
        //开始搜索
        int tar =0,pos =0;
        while(tar<s.length()&&pos<p.length()){
            if(s.charAt(tar)==p.charAt(pos)){
                tar++;
                pos++;
            }else if(pos!=0){
                pos=next[pos-1];
            }else{
                tar++;
            }
        }
        System.out.println(tar-pos);
        return pos==p.length()?tar-pos:-1;
    }
}

 

本文系作者 @ 原创发布在 噓だ。未经许可,禁止转载。

喜欢()
评论 (0)
热门搜索
37 文章
3 评论
11 喜欢
Top