Cod sursa(job #3263605)

Utilizator vladm98Munteanu Vlad vladm98 Data 15 decembrie 2024 14:36:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

int Z[4000005];
void buildZ(string &a) {
    Z[0] = 0;
    int best = 0; // cel mai bun Z so far

    for (int i = 1; i < a.length(); i++) {
        if (i <= best + Z[best] - 1) { // daca i ul se afla in interiorul celui mai bun Z de pana acum
            Z[i] = min(best + Z[best] - i, Z[i - best]);
        }

        while (a[i + Z[i]] == a[Z[i]]) {
            Z[i]++;
        }

        if (best + Z[best] < i + Z[i]) {
            best = i;
        }
    }
}


signed main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string a, b;
    cin >> a >> b;
    int counter = 0;
    vector <int> pos;

    int targetSize = a.size();

    a += '$';
    a += b;

    buildZ(a);

    for (int i = 0; i < a.size(); i++) {
        if (Z[i] == targetSize) {
            counter += 1;

            if (pos.size() == 1000) continue;
            pos.push_back(i - targetSize - 1);
        }
    }

    cout << counter << '\n';

    for (auto x : pos) {
        cout << x << ' ';
    }
}