题目描述

blablabla

样例

blablabla

算法1

blablabla

时间复杂度

参考文献

Java 代码

import java.io.*;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] next; // next数组

    public static void main(String[] args) throws IOException {
        // 对输入数据进行初始化
        int n = Integer.parseInt(reader.readLine()); // 模板串的长度
        String str2 = reader.readLine();

        int m = Integer.parseInt(reader.readLine()); // 被匹配字符串的长度
        String str1 = reader.readLine();
        next = kmpNext(str2);
        for(int i = 0, j = 0;i < str1.length(); i++){
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if(j == str2.length()){
              writer.write(i - j + 1 + " "); // 将 s串中起点的位置写入 
              j = next[j-1];
            }
        }

        writer.flush();    
        reader.close();
        writer.close();
    }

    private static int[] kmpNext(String str){
        int[] next = new int[str.length()];
        for(int i = 1, j = 0;i<str.length();i++){
            while(j > 0 && str.charAt(i) != str.charAt(j)){
                j = next[j-1];
            }
            if(str.charAt(i) == str.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}