Cod sursa(job #2749769)

Utilizator TanasucaGeorgeAlexandruTanasucaGeorgeAlexandru TanasucaGeorgeAlexandru Data 8 mai 2021 10:13:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>
#define P 9987671
#define Q 9981121
using namespace std;
/**
P = 34512773, 123457, 777013
De evitat:
2000000000000000000 :
30000000000000000000000 : 100 = rest 0

Hash:
- tabele de hash (tabele de dispersie)
- cod hash

0-9 : 0..9
a-z : 10..35
A-Z : 36..61
-------
62 de caractere

210
ABA = (A*62+B)*62 + A
ABA = A*62^2 + B * 62^1 + A*62^0 = H = 36*62*62+37*62+36 : P
CABBCABABAB

h1 = CAB
h1 = ((h1 - C * 62^2 + P)*62 + B) % P

72345
h1 = ((723 - 7*100) * 10 + 4) % P

543210
234102 (baza b=5) = 2*b^5+3*b^4+...
*/

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002];
char b[2000002];
int n;
int cod[256];
int poz[1005], m;

int main()
{
    int j, i, h,H, h1,h2, PW = 1, pw = 1, nrPotriviri = 0;
    j = 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 = H = 0;
    for (n = 0; a[n] != 0; n++)
    {
        h = (h * 62 + cod[a[n]]) % P;
        H = (H * 62 + cod[a[n]]) % Q;
    }
    for (i = 1; i < n; i++)
    {
        pw = pw * 62 % P;
        PW = PW * 62 % Q;
    }

    /// parcurg fiecare secventa de lungime n din b
    /// formez primul cod h1 cu primele n car. din b
    h1 = h2 = 0;
    for (i = 0; i < n; i++)
    {
        h1 = (h1 * 62 + cod[b[i]]) % P;
        h2 = (h2 * 62 + cod[b[i]]) % Q;
    }
    if (h == h1 && H == h2)
    {
        nrPotriviri++;
        poz[++m] = 0;
    }
    for (i = n; b[i] != 0; i++)
    {
        h1 = ((h1 - cod[b[i-n]] * pw % P + P) * 62 + cod[b[i]]) % P;
        h2 = ((h2 - cod[b[i-n]] * PW % Q + Q) * 62 + cod[b[i]]) % Q;
        if (h == h1 && H == h2)
        {
            nrPotriviri++;
            if (m < 1000) poz[++m] = i - n + 1;
        }
    }
    fout << nrPotriviri << "\n";
    for (i = 1; i <= m; i++)
        fout << poz[i] << " ";
    fout.close();
    return 0;
}