Cod sursa(job #3041428)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 31 martie 2023 15:03:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

#define GARDA fin.close(); fout.close(); exit(0);

using namespace std;

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

int const N(2e6 + 5), K(1000);

char A[N], B[N], s[2 * N];
int pi[2 * N], a, b, n, res[K + 1], cnt;

inline void Pi() {
    int j = 0;
    for (int i = 2; i <= n; ++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 >> B;
    a = static_cast<int>(strlen(A));
    b = static_cast<int>(strlen(B));

    for (int i = 0; i < a; ++i)
        s[++n] = A[i];
    s[++n] = '$';
    for (int i = 0; i < b; ++i)
        s[++n] = B[i];

    Pi();

    for (int i = a + 2; i <= n; ++i) {
        if (pi[i] != a)
            continue;
        ++cnt;
        if (cnt <= K)
            res[cnt] = i - 2 * a - 1;
    }

    fout << cnt << '\n';
    for (int i = 1; i <= min(cnt, K); ++i)
        fout << res[i] << ' ';

	GARDA
}