题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式
第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围
1≤N≤105
1≤M≤106
输入样例：

3
aba
5
ababa

输出样例：

0 2

算法1

思路

字符串坐标从1开始：即next[i] = i位置最长的相同前缀后缀的长度 = 最长前缀结尾坐标

i是s字符串上的坐标，j是p字符串上的坐标，每次s[i]和p[j + 1]进行比较

时间复杂度

参考文献

Java 代码

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

public class Main {
    private static int N = 100010;
    private static char[] p = new char[N];
    private static int[] ne = new int[N];
    private static int M = 1000010;
    private static char[] s = new char[M];
    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        String str = reader.readLine();
        for(int i = 1;i < n + 1;i++){
            p[i] = str.charAt(i - 1);
        }
        int m = Integer.parseInt(reader.readLine());
        str = reader.readLine();
        for(int i = 1;i < m + 1;i++){
            s[i] = str.charAt(i - 1);
        }

        //求next数组,next[1]为0不用算
        for(int i = 2,j = 0;i < n + 1;i++){
            while(j != 0 && p[i] != p[j + 1]){
                j = ne[j];
            }
            if(p[i] == p[j + 1]){
                j++;
            }
            ne[i] = j;
        }
        //kmp匹配过程，j总是在i前面一个位置
        for(int i = 1,j = 0;i < m + 1;i++){
            while(j != 0 && s[i] != p[j + 1]){
                j = ne[j];
            }
            if(s[i] == p[j + 1]){
                j++;
            }
            while(j == n){
                writer.write(i - n + " ");
                j = ne[j];
            }
        }
        writer.flush();
        writer.close();
        reader.close();
    }

}