P3375 【模板】KMP字符串匹配

KMP算法

题目：https://www.luogu.com.cn/problem/P3375

    public static void kmp_search(String s1, String s2){
        if (s2.isEmpty()) System.out.println("-1");

        int n = s1.length();
        int m = s2.length();

        String ss1 = " "+s1;
        String ss2 = " "+s2;
        char str1[] = ss1.toCharArray();
        char str2[] = ss2.toCharArray();

        //next数组
        int next[] = new int[m + 1];
        for (int i = 2, j = 0; i <= m; i++){
            while (j > 0 && str2[i] != str2[j + 1]) j = next[j];
            if (str2[i] == str2[j + 1]) j++;
            next[i] = j;
        }

        //匹配过程
        for (int i = 1, j = 0; i <= n; i++){
            while (j > 0 && str1[i] != str2[j + 1]) j = next[j];
            if (str1[i] == str2[j + 1]) j++;
            if (j == m){
                System.out.println(i - m + 1);
                j = 0;
                i = i - m + 1;
            }
        }