Cod sursa(job #2574058)

Utilizator RagnoRazvan Petec Ragno Data 5 martie 2020 20:09:36
Problema Ciurul lui Eratosthenes Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define input "strmatch.in"
#define output "strmatch.out"

const int lMax = 2000005;

using namespace std;

char a[lMax], b[lMax];
int lga, k, lgb, ans1;
int pi[lMax];
vector <int> ans2;

main()
{
    ifstream cin(input);
    ofstream cout(output);

    cin >> a + 1 >> b + 1;
    lga = strlen(a + 1);
    lgb = strlen(b + 1);

    k = 0;

    for (int i = 2; i <= lga; ++i)
    {
        k = pi[i - 1];
        while (k && a[k + 1] != a[i])
            k = pi[k];

        if (a[k + 1] == a[i])
            ++k;
        pi[i] = k;
    }

    k = 0;

    for (int i = 1; i <= lgb; ++i)
    {
        while (k && a[k + 1] != b[i])
            k = pi[k];
        if (a[k + 1] == b[i])
            ++k;
        if (k == lga)
        {
            ++ans1;
            if (ans2.size() < 1000)
                ans2.emplace_back(i - lga);
        }
    }

    cout << ans1 << "\n";
    for (auto i : ans2)
        cout << i << " ";

    return 0;
}