题目描述

blablabla

样例

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int lenp=Integer.parseInt(sc.nextLine());
        String p=sc.nextLine();
        int lens=Integer.parseInt(sc.nextLine());
        String s=sc.nextLine();
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int[] next=new int[lenp];
        next[0]=-1;
        for (int i = 1,j=-1; i <lenp ; i++) {
            while(j!=-1&&p.charAt(j+1)!=p.charAt(i))
                j=next[j];
            if (p.charAt(j+1)==p.charAt(i))
                j++;
            next[i]=j;

        }
        for (int i = 0,j=0; i <lens ; i++) {

            while(j!=0&&s.charAt(i)!=p.charAt(j)){
                j=next[j-1]+1;
            }
            if (s.charAt(i)==p.charAt(j))j++;
            if (j==lenp){
                bw.write(i-lenp+1+" ");
                j=next[j-1]+1;

            }
        }
         bw.flush();
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla