Cod sursa(job #2592426)

Utilizator OnofreiTudorOnofrei Tudor OnofreiTudor Data 1 aprilie 2020 18:06:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>

#define PRIM 699967

using namespace std;

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

char N[2000005], M[2000005];
int i, n, m, valori, p[1005];
long long putere, hash1, hash2, val;

int main()
{
    fin >> M >> N;
    putere = 1;
    n = strlen(N);
    m = strlen(M);
    hash1 = 0;
    for(i = 0; i<m; i++){
        hash1 = (hash1 * 29 + M[i]-'A') % PRIM;
        putere *= 29;
    }
    hash2 = 0;
    for(i = 0; i<=m-1; i++){
        hash2 = (hash2 * 29 + N[i]-'A') % PRIM;
    }
    if(hash1 == hash2){
        valori++;
        p[valori] = 0;
    }
    for(i = 1; i<=n-m && valori <= 1000; i++){
        hash2 = ((hash2 - (N[i-1]-'A')*(putere/29)) * 29 + N[i+m-1]-'A') % PRIM;
        if(hash1 == hash2){
            valori++;
            p[valori] = i;
        }
    }
    fout << valori << '\n';
    for(i = 1; i<=valori; i++){
        fout << p[i] << ' ';
    }

    return 0;
}