KMP算法

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        if(str1.length < str2.length){
            System.out.println(-1);
        }else{
            StringBuilder sb = new StringBuilder();
            int[] next = getNextArr(str2);
            int i1 = 0, i2 = 0;
            int find = kmp(str1, str2, i1, i2, next);
            while(find > -1){
                sb.append(find + " ");
                i1 = find + 1;      // i1不断后移，与str2匹配
                find = kmp(str1, str2, i1, i2, next);
            }
            System.out.println(sb.length() == 0? -1: sb.toString().trim());
        }
    }
    
    private static int kmp(char[] str1, char[] str2, int i1, int i2, int[] next) {
        if(i1 + str2.length >= str1.length) return -1;
        while(i1 < str1.length && i2 < str2.length){
            if(str1[i1] == str2[i2]){      // 字符相等，两个字符都移动
                i1 ++;
                i2 ++;
            }else if(next[i2] > -1){
                i2 = next[i2];     // 不相等且还能往前跳，则i2往前面跳
            }else{
                i1 ++;             // str2已经跳到0了还没法匹配成功，就只能移动str1的指针了
            }
        }
        return i2 == str2.length? i1 - i2: -1;
    }
    
    private static int[] getNextArr(char[] str) {
        if(str.length == 1) return new int[]{-1};
        int[] next = new int[str.length];
        next[0] = -1;
        int i = 2, prev = 0;
        while(i < str.length){
            if(str[i - 1] == str[prev]){
                next[i] = prev + 1;       // 最长与后缀相等的前缀长度+1
                prev ++;
                i ++;
            }else if(prev > 0){
                prev = next[prev];       // 不相等就往前跳
            }else{
                next[i] = prev;
                i ++;
            }
        }
        return next;
    }
}