算法1

注意：
① 自己的学习笔记。在idea上测试的，没有改成适用于acwing平台的代码。直接复制运行不可得到acwing平台想要的结果。

// 串s和串p进行匹配
static void search() {
    for (int i = 0, j = 0; i < s.length; i++) {
        // 如果i j指向的数字不相等，那么j进行缩减
        while (j != 0 && s[i] != p[j]) j = nxt[j - 1];
        // 上一个while结束时候，j==0 或者 s[i] == p[j]
        // ①j==0时候需要比较s[i] 和p[j] ，如果不等拉倒，等的话j++;
        // ②j!=0时候一定有sp[i] == p[j]，等的话j++;
        if (s[i] == p[j]) j++;
        if (j == p.length) {
            // 结束上一个if以后，j++了，此时i还没有i++，因此i-j+1
            System.out.println(i - j + 1);
            j = nxt[j - 1];
        }
    }
}

// 建立nxt[]
static void buildNxt() {
    // i 看成长串的尾部， j看成短串的尾部
    for (int i = 1, j = 0; i < p.length; i++) {
        while (j != 0 && p[i] != p[j]) j = nxt[j - 1];
        // 上一个while结束时候，j==0 或者 p[i] == p[j]
        // ①j==0时候需要比较p[i] 和p[j] ，如果不等拉倒，等的话j++;
        // ②j!=0时候一定有p[i] == p[j]，j++;
        if (p[i] == p[j]) j++;
        // 更新nxt
        nxt[i] = j;
    }
}

// 完整代码
import java.util.*;
public class Main {
    static char[] s = "abcabdddabcabc".toCharArray();
    static char[] p = "abc".toCharArray();
    static int[] nxt = new int[p.length]; // 辅助数组：存储着p[0] - p[i]子串的前端后端最长字符长度

    public static void main(String[] args) {
        buildNxt();
        search();
    }

    static void search() {
        for (int i = 0, j = 0; i < s.length; i++) {
            // 如果i j指向的数字不相等，那么j进行缩减
            while (j != 0 && s[i] != p[j]) j = nxt[j - 1];
            // 上一个while结束时候，j==0 或者 s[i] == p[j]
            // ①j==0时候需要比较s[i] 和p[j] ，如果不等拉倒，等的话j++;
            // ②j!=0时候一定有sp[i] == p[j]，等的话j++;
            if (s[i] == p[j]) j++;
            if (j == p.length) {
                // 结束上一个if以后，j++了，此时i还没有i++，因此i-j+1
                System.out.println(i - j + 1);
                j = nxt[j - 1];
            }
        }
    }
    static void buildNxt() {
        // i 看成长串的尾部， j看成短串的尾部
        for (int i = 1, j = 0; i < p.length; i++) {
            while (j != 0 && p[i] != p[j]) j = nxt[j - 1];
            // 上一个while结束时候，j==0 或者 p[i] == p[j]
            // ①j==0时候需要比较p[i] 和p[j] ，如果不等拉倒，等的话j++;
            // ②j!=0时候一定有p[i] == p[j]，j++;
            if (p[i] == p[j]) j++;
            // 更新nxt
            nxt[i] = j;
        }
    }
}