2、KMP算法&字符串子串位置

AcWing 831. KMP字符串

2022.9.11 上午力扣周赛ac3道，kmp算法一直调到了下午4:55才ac全部用例，以此纪念

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.KMP();
        bw.flush();
        br.close();
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    void KMP() throws IOException {
        String len_p = br.readLine();
        String p = br.readLine();
        String len_s = br.readLine();
        String s = br.readLine();
        //pp是模式字符数组
        //ss是长的字符数组
        char[] ss_temp = s.toCharArray();
        char[] ss = new char[ss_temp.length + 1];
        char[] pp = p.toCharArray();
        int[] next = new int[pp.length];
        next[0] = 0;
        for (int i = 0; i < ss_temp.length; i++) ss[i + 1] = ss_temp[i];
        for (int i = 0; i < pp.length; i++) cal_next(pp, next, i);
        for (int i = 1, j = 0; i < ss.length; ) {
            while (j > 0 && pp[j] != ss[i]) j = next[j];
            //j已经退到无路可退了，无论相等不相等都i++
            if (pp[j] == ss[i++]) j++;
            if (j == pp.length - 1&&i<ss.length&&pp[j] == ss[i]) {
                j = next[j];
                if (i < ss.length)
                    bw.write(i - pp.length + " ");
            }
        }
    }

    void cal_next(char[] pp, int[] next_new, int pos) {
        if (pos == 0 || pos == 1) {
            next_new[pos] = 0;
            return;
        }
        int m = pos - 1;
        if (pp[next_new[m]] == pp[m]) {
            next_new[pos] = next_new[m] + 1;
        } else {
            int t = next_new[m];
            while (t > 0 && pp[next_new[t]] != pp[m]) {
                t = next_new[t];
            }
            if (pp[next_new[t]] == pp[m]) {
                next_new[pos] = next_new[t] + 1;
            } else {
                next_new[pos] = 0;
            }
        }
    }
}