乐趣区

关于java:KMP算法Java实现

public class KMP {public static void main(String[] args) {
        String string = "abxabcabcaby";
        String pattern = "abcaby";
        int[] next = KMP_next(pattern);
        System.out.println(Arrays.toString(next));
        int searchRes = KMP_search(string, pattern, next);
        System.out.println(searchRes);
    }

    public static int[] KMP_next(String p){
        // 初始化 next 数组
        int[] next = new int[p.length()];
        // 数组第一位肯定是 0
        next[0] = 0;
        int j = 0, i = 1;
        while (i < next.length) {if (p.charAt(i) == p.charAt(j)){
                ++j;
                next[i] = j;
                i++;
            } else {if (j == 0) {next[i] = j;
                    i++;
                    continue;
                }
                j = next[j - 1];
            }
        }
        return next;
    }

    public static int KMP_search(String s, String p, int[] next){
        int i = 0, j = 0;
        while (i < s.length()){if (j == p.length() - 1 && s.charAt(i) == p.charAt(j)){return i - j;}
            if (s.charAt(i) == p.charAt(j)){
                i++;
                j++;
            } else {if (j == 0){
                    i++;
                    continue;
                }
                j = next[j - 1];
            }
        }
        return -1;
    }
}
退出移动版