1.思路

我们这题如果直接暴力的话，先用i,j分别遍历母串和子串，如果相同则i，j都往后面继续匹配；如果不相同，那么就使i回到原来的位置+1，j又从子串起点位置开始匹配。我们会发现其实有一些数会遍历n次，所以我们有没有办法能只遍历母串一次呢？那我们就要用到KMP算法。其实KMP算法就是预先处理子串，使得当我们和母串匹配不成功时不直接回溯到原来位置，而是回到子串预处理指向的位置，这样我们就可以只遍历母串一遍就能完成题目要求。

2.代码模板

import java.util.*;
import java.io.*;
public class Main {
    static int N = 100010, M = 1000010;
    static int n, m;
    static int[] ne = new int[N];   //表示如果当前匹配失败，下一次从哪个位置开始匹配
    static char[] s = new char[M];  //母串（比较长的）
    static char[] p = new char[N];  //子串（短的）
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(br.readLine());
        String str = br.readLine();
        for (int i = 0; i < n; i++) 
            p[i] = str.charAt(i);
        m = Integer.parseInt(br.readLine());
        str = br.readLine();
        for (int i = 0; i < m; i++) 
            s[i] = str.charAt(i);
        ne[0] = -1;     //第一个元素如果匹配失败那么他下一次也只能从第一个元素开始匹配
        for (int i = 1, j = -1; i < n; i ++ ) { //初始化ne数组
            while (j != -1 && p[i] != p[j + 1]) //如果p[i]和p[j+1]不匹配，那么我们就回溯到上一个ne数组指向的位置，直到匹配或者到第一个位置
                j = ne[j];
            if (p[i] == p[j + 1])   //匹配成功，j往后移 
                j ++ ;
            ne[i] = j;  //记录ne[i]，表示如果匹配不成功，可以回溯到第j个位置
        }
        for (int i = 0, j = -1; i < m; i ++ ) {
            while (j != -1 && s[i] != p[j + 1])//匹配失败则回溯到上一个ne数组指向的位置，直到匹配或者到第一个位置
                j = ne[j];
            if (s[i] == p[j + 1]) //匹配成功
                j ++ ;
            if (j == n - 1){    //完全匹配，则输出答案
                bw.write(i - j + " ");  
                j = ne[j];  //并且回溯到上一个位置往下匹配
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

3.复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)