Cod sursa(job #3224529)

Utilizator ililogIlinca ililog Data 15 aprilie 2024 16:22:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>

#define NMAX 2000000

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

#define P 73
#define MOD1 100007
#define MOD2 100021

char A[NMAX+5], B[NMAX+5];
int la, lb;
int hashA1, hashA2, hashB1, hashB2, nr;
bool match[NMAX+5];

int main() {
    
    fin >> A >> B;
    la = strlen(A);
    lb = strlen(B);
    
    if (la > lb) {
        fout << "0\n";
        return 0;
    }
    
    int powP1 = 1, powP2 = 1;
    for (int i = 0; i<la; i++) {
        hashA1 = (hashA1*P + A[i])%MOD1;
        hashA2 = (hashA2*P + A[i])%MOD2;
        hashB1 = (hashB1*P + B[i])%MOD1;
        hashB2 = (hashB2*P + B[i])%MOD2;
        if (i != 0) powP1 = (powP1 * P) % MOD1;
        if (i != 0) powP2 = (powP2 * P) % MOD2;
    }
    
    if (hashA1 == hashB1 && hashA2 == hashB2) {
        match[0] = 1;
        nr++;
    }
    
    for (int i = la; i<lb; i++) {
        hashB1 = (((hashB1 - B[i-la]*powP1) % MOD1 + MOD1) * P + B[i]) % MOD1;
        hashB2 = (((hashB2 - B[i-la]*powP2) % MOD2 + MOD2) * P + B[i]) % MOD2;
        if (hashA1 == hashB1 && hashA2 == hashB2) {
            match[i-la+1] = 1;
            nr++;
        }
    }
    
    fout << nr << "\n";
    
    nr = 0;
    for (int i = 0; i<lb && nr < 1000; i++) {
        if (match[i]) {
            fout << i << " ";
            nr++;
        }
    }
    
    return 0;
}