Cod sursa(job #3001656)

Utilizator tomaionutIDorando tomaionut Data 13 martie 2023 20:26:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define P 100007
#define Q 100021
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005];
char b[2000005];
int sol[1005];
int n, m, h1, H1, h2, H2, pow1 = 1, pow2 = 1, nr;
int main()
{
    int i;
    fin >> (a + 1) >> (b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for (i = 1; i <= n; i++)
    {
        h1 = (h1 * 73 + a[i]) % P;
        H1 = (H1 * 73 + a[i]) % Q;

        h2 = (h2 * 73 + b[i]) % P;
        H2 = (H2 * 73 + b[i]) % Q;
        if (i != 1)
        {
            pow1 = pow1 * 73 % P;
            pow2 = pow2 * 73 % Q;
        }
    }

    if (h1 == h2 and H1 == H2)
    {
        nr++;
        sol[nr] = 0;
    }

    for (i = n + 1; i <= m; i++)
    {
        h2 = ((h2 - b[i - n] * pow1 % P + P) * 73 + b[i]) % P;
        H2 = ((H2 - b[i - n] * pow2 % Q + Q) * 73 + b[i]) % Q;
        if (h1 == h2 and H1 == H2)
        {
            nr++;
            if (nr <= 1000)
                sol[nr] = i - n;
        }
    }
    fout << nr << "\n";
    for (i = 1; i <= min(nr, 1000); i++)
        fout << sol[i] << " ";
    return 0;
}