Cod sursa(job #2749754)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 8 mai 2021 10:05:30
Problema Potrivirea sirurilor Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define  P 9987671
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char a[2000002];
char b[2000002];
int n , m;
int cod[256];
vector <int> poz;

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

    }
    fout << nrPotriviri << "\n";
    for (auto j : poz)
        fout << j << " ";
    return 0;
}