https://www.acwing.com/problem/content/833/

#include<iostream>
using namespace std;

const int N=100010,M=1000010;

int n,m;
int ne[N];  //next array
char s[M],p[N];


int main(){
    cin>>n>>p+1>>m>>s+1; // index start at 1
    // make next[], for substring
    for(int i=2,j=0 ;i<=n ;i++){
        while(j && p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    
    //matching
    for(int i=1,j=0;i<=m;i++){
        while(j!=0 && s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n){ //matched
            cout<<i-n<<" "; 
            j=ne[j];
        }
    }
}