Cod sursa(job #3037837)

Utilizator IaaanAnghel Georgian Bogdan Iaaan Data 26 martie 2023 15:53:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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;
const ull mod = 1e9 + 7;
ull r[256];
ull hshB1[NMAX + 5], hshB2[NMAX + 5];
ull p1[NMAX + 5], p2[NMAX + 5];

int main()
{
    p1[0] = p2[0] = 1;
    for (int i=1; i<=NMAX; i++)
        p1[i] = p1[i-1] * P, p2[i] = p2[i-1] * P % mod;

    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;

    ull hshA1 = 0, hshA2 = 0;
    for (int i=1; i<=n; i++)
        {
            hshA1 = hshA1 * P + r[a[i]];
            hshA2 = (hshA2 * P % mod + r[a[i]]) % mod;
        }
    for (int i=1; i<=m; i++)
        {
            hshB1[i] = hshB1[i-1] * P + r[b[i]];
            hshB2[i] = (hshB2[i-1] * P % mod + r[b[i]]) % mod;
        }

    vector<int>ans;

    for (int i=n; i<=m; i++)
    {
        if ((hshA1 == hshB1[i] - hshB1[i-n] * p1[n]) && (hshA2 == (hshB2[i] - hshB2[i-n] * p2[n] % mod + mod) % mod))
        {
            if (ans.size() < 1000)
                ans.push_back(i-n);
            else
                break;
        }
    }

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


    return 0;
}