Cod sursa(job #2809570)

Utilizator Chiri_Robert Chiributa Chiri_ Data 27 noiembrie 2021 10:53:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Hash
{
    long long v, mod, n, len, v0;
    long long val;

    Hash(long long v, long long mod, long long n)
      : v(v), mod(mod), n(n), val(0), v0(1)
    {}

    void init(char *s)
    {
        len = strlen(s);
        for (long long i = n - 1; i >= 0; i--) {
            val = (val + (1ll * s[i] * v0) % mod) % mod;
            if (i) {
                v0 = (v0 * v) % mod;
            }
        }
    }

    void next(char r, char a)
    {
        val = (((val - (1ll * r * v0) % mod + mod) * v) % mod + a) % mod;
    }
};

char a[2000001], b[2000001];
long long l1, l2;
int val[1001], nr;

int main()
{
    fin >> b >> a;
    l1 = strlen(b);
    l2 = strlen(a);

    Hash b1(31, 40099, l1), b2(53, 319993, l1);
    Hash a1(31, 40099, l1), a2(53, 319993, l1);

    b1.init(b);
    b2.init(b);
    a1.init(a);
    a2.init(a);
    if (b1.val == a1.val && b2.val == a2.val) {
        val[nr++] = 0;
    }
    for (long long i = l1; i < l2; i++) {
        a1.next(a[i - l1], a[i]);
        a2.next(a[i - l1], a[i]);
        if (b1.val == a1.val && b2.val == a2.val) {
            if (nr <= 1000) {
                val[nr++] = i - l1 + 1;
            } else {
                nr++;
            }
        }
    }

    fout << nr << '\n';
    nr = min(nr, 1000);
    for (int i = 0; i < nr; i++) {
        fout << val[i] << " ";
    }
}