Cod sursa(job #2910366)

Utilizator Frant_IoanaFrant Ioana Frant_Ioana Data 20 iunie 2022 08:26:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
string a, b;
int NA, NB, cnt;
char match[2000001];

int main(){
    fin >> a >> b;
    NA = a.size();
    NB = b.size();

    if(NA > NB)
        fout << 0;
    else{
        int hashA1 = 0, hashA2 = 0, P1 = 1, P2 = 1, P = 73, MOD1 = 100007, MOD2 = 100021;

        for(int i = 0; i < NA; i++){
            hashA1 = (hashA1 * P + a[i]) % MOD1;
            hashA2 = (hashA2 * P + a[i]) % MOD2;

            if(i != 0){
                P1 = (P1 * P) % MOD1;
                P2 = (P2 * P) % MOD2;
            }
        }

        int hash1 = 0, hash2 = 0;

        for(int i = 0; i < NA; i++){
            hash1 = (hash1 * P + b[i]) % MOD1;
            hash2 = (hash2 * P + b[i]) % MOD2;
        }

        if(hashA1 == hash1 && hashA2 == hash2)
            match[0] = 1, cnt++;

        for(int i = NA; i < NB; i++){
            hash1 = ((hash1 - (b[i - NA] * P1) % MOD1 + MOD1) * P + b[i]) % MOD1;
            hash2 = ((hash2 - (b[i - NA] * P2) % MOD2 + MOD2) * P + b[i]) % MOD2;

            if(hash1 == hashA1 && hash2 == hashA2)
                match[i - NA + 1] = 1, cnt++;
        }

        fout << cnt << '\n';

        cnt = 0;
        for(int i = 0; i < NB && cnt < 1000; i++)
            if(match[i])
                cnt++, fout << i << ' ';
    }
}