KMP string

Given a pattern string S, And a template string P, All strings contain only uppercase and lowercase letters and Arabic numerals .

Template string P In mode string S Appears as a substring many times in .

Find the template string P In mode string S The starting subscript of all positions appearing in .

Input format

Enter the integer in the first line N, Representation string P The length of .

The second line of input string P.

In the third line, enter the integer M, Representation string S The length of .

On the fourth line, enter the string S.

Output format

All in one line , Output the starting subscript of all occurrences （ Subscript from  0  Start counting ）, Integers are separated by spaces .

Data range

1≤N≤1e5
1≤M≤1e6

sample input ：

3
aba
5
ababa

sample output ：

0 2

Code:

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

typedef int Status;

const int N = 10000010;

int n, m;
int ne[N];
char s[N], p[N];

signed main()
{
	cin >> n >> p + 1 >> m >> s + 1;
	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;
	}
	for(int i = 1, j = 0; i <= m; i ++ )
	{
		while(j && s[i] != p[j + 1])  j = ne[j];
		if(s[i] == p[j + 1])  j ++;
		if(j == n)
		{
			cout << i - n << ' ';
			j = ne[j]; // j Point to the last letter of successful matching 
		}
	}
}