Cod sursa(job #2749755)

Utilizator Stefan_BircaBirca Stefan Stefan_Birca Data 8 mai 2021 10:06:44
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define P 9987671

using namespace std;

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

int n, m;
char a[2000005];
char b[2000005];
int cod[256];
int poz[1005];

int main()
{
    int i, h1, h, j = 0, pw = 1, nrPotriviri = 0;
    for (i = '0'; i <= '9'; i++) cod[i] = j++;
    for (i = 'a'; i <= 'z'; i++) cod[i] = j++;
    for (i = 'A'; i <= 'Z'; i++) cod[i] = j++;
    fin >> a >> b;
    /// construim pe h
    h = 0;
    for (n = 0; a[n] != 0; n++)
        h = (h * j + cod[a[n]]) % P;
    for (i = 1; i < n; i++)
        pw = pw * j % P;
    /// parcurg fiecare secventa de lungime n din b
    /// formez primul cod h1 cu primele n char din b
    h1 = 0;
    for (i = 0; i < n; i++)
        h1 = (h1 * j + cod[b[i]]) % P;
    if (h == h1)
    {
        nrPotriviri++;
        poz[++m] = 0;
    }
    int p;
    for (i = n; b[i] != 0; i++)
    {
        h1 = ((h1 - cod[b[i - n]] * pw % P + P) * j + cod[b[i]]) % P;
        if (h == h1)
        {
            nrPotriviri++;
            if (m < 1000) poz[++m] = i - n + 1;
        }
    }
    fout << nrPotriviri << "\n";
    for (i = 1; i <= m; i++)
        fout << poz[i] << " ";
    fout << "\n";
    fin.close();
    fout.close();

    return 0;
}