KMP算法

#include<bits/stdc++.h>
// #define int long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
const int N = 1e5 + 10;
const int M = 1e6 + 10;
char s[M], p[N];
int n, m;
int ne[N];
void get_next() { // 求 next 数组
  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;
  }
}
void kmp() {
  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) {
      printf("%d ", i - n );
    }
  }
}
void solve() {
  cin >> n >> p + 1;
  cin >> m >> s + 1;
  get_next();
  kmp();
}
signed main() {
  // int t; cin >> t;
  // while (t--)
  solve();
  return 0;
}