Cod sursa(job #3224507)

Utilizator ililogIlinca ililog Data 15 aprilie 2024 15:53:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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 MOD 100007

char A[NMAX+5], B[NMAX+5];
int la, lb;
int hashA, hashB, 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 powP = 1;
    for (int i = 0; i<la; i++) {
        hashA = (hashA*P + A[i])%MOD;
        hashB = (hashB*P + B[i])%MOD;
        if (i != 0) powP = (powP * P) % MOD;
    }
    
    if (hashA == hashB) {
        match[0] = 1;
        nr++;
    }
    
    for (int i = la; i<lb; i++) {
        hashB = (((hashB - B[i-la]*powP) % MOD + MOD) * P + B[i]) % MOD;
        if (hashA == hashB) {
            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;
}