Cod sursa(job #2881717)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 30 martie 2022 19:17:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;

string const& task("strmatch");
ifstream fin(task + ".in");
ofstream fout(task + ".out");

int const N(2e6 + 5);

char A[N], B[N], S[2 * N];
int a, b, s, pi[2 * N];

void PF() {
    int j = 0;
    for (int i = 2; i <= s; ++i) {
        while (j && S[i] != S[j + 1])
            j = pi[j];
        if (S[i] == S[j + 1]) ++j;
        pi[i] = j;
    }
}

signed main() {

    fin >> (A + 1) >> (B + 1);
    a = static_cast<int>(strlen(A + 1));
    b = static_cast<int>(strlen(B + 1));
    for (int i = 1; i <= a; ++i)
        S[++s] = A[i];
    S[++s] = '$';
    for (int i = 1; i <= b; ++i)
        S[++s] = B[i];
    PF();
    int res = 0;
    for (int i = a + 2; i <= s; ++i)
        if (pi[i] == a)
            ++res;
    fout << res << '\n';
    res = min(res, 1000);
    for (int i = a + 2; i <= s; ++i)
        if (pi[i] == a) {
            fout << i - 2 * a - 1 << ' ';
            if (--res == 0) break;
        }

    return 0;
}