Cod sursa(job #3037827)

Utilizator IaaanAnghel Georgian Bogdan Iaaan Data 26 martie 2023 15:42:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e6;

using ull = unsigned long long;
const ull P = 13331;
ull r[256];
ull hsh1[NMAX + 5];
ull hsh2[NMAX + 5];
ull p[NMAX + 5];

int main()
{
    p[0] = 1;
    for (int i=1; i<=NMAX; i++)
        p[i] = p[i-1] * P;

    for (int i=0; i<256; i++)
        r[i] = (ull) rand() * rand() * rand() * rand();

    string a, b;
    in >> a >> b;

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

    int n = (int)a.size() - 1;
    int m = (int)b.size() - 1;

    for (int i=1; i<=n; i++)
        hsh1[i] = hsh1[i-1] * P + r[a[i]];
    for (int i=1; i<=m; i++)
        hsh2[i] = hsh2[i-1] * P + r[b[i]];

    vector<int>ans;

    for (int i=n; i<=m; i++)
    {
        if (hsh1[n] == hsh2[i] - hsh2[i-n] * p[n])
        {
            if (ans.size() < 1001)
                ans.push_back(i-n);
            else
                break;
        }
    }

    out << ans.size() << '\n';
    for (int x : ans)
        out << x << ' ';


    return 0;
}