SPOJ NHAY

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

vector<int> computePrefixes(string s) {
    vector<int> ret(s.length());
    for(int i = 1, k = 0; i < s.length(); i++) {
        while(k > 0 && s[k] != s[i]) {
            k = ret[k-1];
        }
        if(s[k] == s[i]) {
            ret[i] = ++k;
        }
        else {
            ret[i] = k;
        }
    }
    return ret;
}

void kmp(string s, string p) {
    vector<int> pre = computePrefixes(p);
    for(int i = 0, k = 0; i < s.length(); i++) {
        while(k > 0 && s[i] != p[k]) {
            k = pre[k-1];
        }
        if(s[i] == p[k]) {
            k++;
        }
        if(k == p.length()) {
            cout << i+1-p.length() << "\n";
            k = pre[k-1];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n;
    string p,s;
    bool first = true;
    while(cin >> n >> p >> s) {
        if(first) {
            first = false;
        }
        else {
            cout << "\n";
        }
        kmp(s,p);
    }


    return 0;
}