KMP

#include <iostream>
#include <cstring>

using namespace std;

void preKMP(string pattern, int f[]) {
    int m = pattern.length(), k;
    f[0] = -1;

    for (int i = 1; i < m; i++) {
        k = f[i - 1];
        while (k >= 0) { if (pattern[k] == pattern[i - 1]) break; else k = f[k]; }
        f[i] = k + 1;
    }
}

int KMP(string pattern, string target) {
    int i = 0, k = 0, m = pattern.length(), n = target.length();
    int f[m];

    preKMP(pattern, f);

    while (i < n) {
        if (k == -1) {
            i++;
            k = 0;
        } else if (target[i] == pattern[k]) {
            i++;
            k++;

            if (k == m) return i - k;
        } else k = f[k];
    }
    return -1;
}

int main() {
    string tar, pat;
    int n = 0, p = 0;

    getline(cin, tar);
    getline(cin, pat);

    while (n < tar.length())
    {
        if (KMP(pat, tar) != -1) {
            cout << KMP(pat, tar) + p << endl;
            p += KMP(pat, tar) + 1;
            tar = tar.substr(KMP(pat, tar) + 1);
        }
        n++;
    }
    return 0;
}