KMP算法

前缀函数

前缀:对于一个字符串，从开始到字符某一个位置的子串。
后缀:对于一个字符串，从字符串某一个位置到结尾的子串。
真前缀:对于一个字符串，从开始到字符某一个位置的子串，不包括字符串本身。
真后缀:对于一个字符串，从字符串某一个位置到结尾的子串，不包括字符串本身。
前缀函数:
给定一个长度为 $n$ 的字符串 $s$ ，其 前缀函数 被定义为一个长度为 $n$ 的数组 $\pi$ 。
其中 $\pi[i]$ 的定义是：

如果子串 $s[0\dots i]$ 有一对相等的真前缀与真后缀： $s[0\dots k-1]$ 和 $s[i - (k - 1) \dots i]$ ，那么 $\pi[i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等：)）的长度，也就是 $\pi[i]=k$ ；
如果不止有一对相等的，那么 $\pi[i]$ 就是其中最长的那一对的长度；
如果没有相等的，那么 $\pi[i]=0$ 。

简单来说 $\pi[i]$ 就是，子串 $s[0\dots i]$ 最长的相等的真前缀与真后缀的长度。

暴力求法：
思路：

枚举字符串的结束位置。
内层循环枚举该子串的最长真前缀与真后缀的长度，然后equals()函数暴力匹配，复杂度 $n^3$

static void pre_function1(String s){
    next[0]=0;
    for(int i=1;i<s.length();i++){//枚举字符串结束位置
        for(int len=i;len>=1;len--){//枚举真前缀真后缀长度
            if(s.substring(0,len).equals(s.substring(i-len+1,i+1))){
                next[i]=len;
                break;
            }
        }
    }
}

优化1
思路:

相邻的前缀函数值至多增加 1。
如果s[i]=s[next[i-1]] (s[next[i-1]]表示前缀已经相同的情况下,第一个还没有比较的字符的位置)
新的位置的值，要不然+1，要不然不变，要不然减少：ababa=>ababab aadbaa=>aadbaaa adadada=>adadadaa
所以这里枚举直接从最大长度位置枚举

static void pre_function2(String s){//
    next[0]=0;
    for(int i=1;i<s.length();i++){//枚举字符串结束位置
        for(int len=next[i-1]+1;len>=1;len--){
            if(s.substring(0,len).equals(s.substring(i-len+1,i+1))){
                next[i]=len;
                break;
            }
        }
    }
}

优化2
思路:

当我新增加一个字符进入，有3种可能，第一种可能，长度是next[i-1]+1，恰好这个新字符加进来后，与s[next[i-1]]这个位置相同（这个是之前计算前缀时，没有被验证成功的位置）。
如果二个位置不相同，那么我希望新的最好的匹配位置，找一个依旧是s[i-1]结尾的后缀，但是长度要稍微短一点。
后缀与前面部分的前缀是相同的，我可以直接去前面前缀的那个位置去找，前面前缀的位置是s[next[i-1]-1]。
那么我在这个位置，我是不是可以找到以该串结尾，长度最大的前缀，但是一定比我这个小一点。

static void pre_function3(String s){
    next[0]=0;
    for(int i=1;i<s.length();i++){
        int len=next[i-1];
        while(len>0&&s.charAt(i)!=s.charAt(len)) len=next[len-1];
        if(s.charAt(i)==s.charAt(len)) len++;
        next[i]=len;
    }
}

KMP

在t串中找出s串出现的位置。
时间复杂度 $o(m+n)$ ，空间复杂度 $o(m+n)$ 。
很简单，有了前缀数组以后，直接构造新字符串s+#+t，对该串s1进行前缀数组构造，然后从s[len(a)]的位置开始遍历到末尾，如果前缀数组的值是len(s)，那么便符合。

时间复杂度 $o(m+n)$ ，空间复杂度 $o(m)$ 。
构造第一个字符串的前缀函数，然后从第二个串开始依次比较
i是第一个字符串的指针
如果第二个串与第一个串在该位置比较相等，那么就i++
如果第二个串与第一个串该位置不相等，那么我们就回溯第一个串，找到前缀的位置，表明后面的比较作废，从该位置再进行比较，如果比较完成，我们再回溯
这里的回溯是指回溯到该位置所对应next[i]值的位置，因为首尾有相同的部分
比如s:abab t:ababab，此时我们第一次比较完成，那么我们s回溯只要回溯到其前缀部分即可，
也就是ab这部分，因为该串已经全部比较完成了，紧接着我们比较后半部分就行。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class KMP字符串 {
    static int zu;
    public static void main(String[] args) {
        zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        String s1=in.next();
        int m=in.nextInt();
        String s2=in.next();
//        getNext(s1,s2);
//        for(int i=n;i<=n+m;i++){
//            if(next[i]==n){
//                out.print(i-2*n+1+" ");
//            }
//        }
        getNext2(s1);
        for(int i=0,j=0;j<m;j++){
           while (i>0&& s1.charAt(i)!=s2.charAt(j)) {
               i=next[i-1];
           }
           if(s1.charAt(i)==s2.charAt(j)) i++;
           if(i==n){
               out.print(j-n+1+" ");
               i=next[i-1];
           }
        }
    }
    static void getNext(String s1,String s2){
        String s3=s1+"#"+s2;
        next[0]=0;
        for(int i=1;i<s3.length();i++){
            int len=next[i-1];
            while(len>0&&s3.charAt(i)!=s3.charAt(len)) len=next[len-1];
            if(s3.charAt(i)==s3.charAt(len)) len++;
            next[i]=len;
        }
    }
    static void getNext2(String s1){
        next[0]=0;
        for(int i=1;i<s1.length();i++){
            int len=next[i-1];
            while(len>0&&s1.charAt(i)!=s1.charAt(len)) len=next[len-1];
            if(s1.charAt(i)==s1.charAt(len)) len++;
            next[i]=len;
        }
    }
    static int next[]=new int[(int) (1e6+1e5+10)];
    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}