Cod sursa(job #3226908)

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

using namespace std;

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

const int NMAX = 2e6;

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

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

    int l = -1, r = -1;
    for (int i = 1; i < a.length(); i++) {
        if (i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }
        while (i + z[i] < a.length() && a[z[i]] == a[i + z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }

    int ans = 0;
    vector<int> pos;

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

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

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