Cod sursa(job #3226911)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 23 aprilie 2024 11:51:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 2e6;

string a, b;
int kmp[2 * NMAX + 1];

void solve() {
    fin >> a >> b;
    int sz = a.length();
    a = a + "#" + b;

    for (int i = 1; i < a.length(); i++) {
        int j = kmp[i - 1];
        while (j > 0 && a[i] != a[j])
            j = kmp[j - 1];
        if (a[i] == a[j])
            j++;
        kmp[i] = j;
    }

    int ans = 0;
    vector<int> pos;

    for (int i = 1; i < a.length(); i++) {
        if (kmp[i] == sz) {
            ans++;
            if (ans <= 1000)
                pos.push_back(i - 2 * sz);
        }
    }

    fout << ans << '\n';
    for (int & x : pos)
        fout << x << ' ';
}

signed main() {
    solve();
    return 0;
}