Cod sursa(job #3039702)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 28 martie 2023 19:42:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;

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

const int b = 256;
const int MOD = 100007;
const int MOD2 = 100021;

string p , t;

vector <int> poz;

int main(){

    fin >> p >> t;

    int n = t.size();
    int m = p.size();

    if(m > n){

        fout << 0;

        exit(0);
    }

    int hashp = 0 , hasht = 0 , h = 1 , hash2p = 0 , hash2t = 0 , h2 = 1;

    for(int i = 0 ; i < m - 1 ; i++){

        h = ( h * b )%MOD;
        h2 = ( h2 * b )%MOD2;
    }

    for(int i = 0 ; i < m ; i++){

        hashp = ((hashp*b)%MOD + p[i])%MOD;
        hasht = ((hasht*b)%MOD + t[i])%MOD;
        hash2p = ((hash2p*b)%MOD2 + p[i])%MOD2;
        hash2t = ((hash2t*b)%MOD2 + t[i])%MOD2;
    }

    int cnt = 0;

    if(hashp == hasht && hash2p == hash2t){

        poz.push_back(0);

        cnt++;
    }

    for(int i = 1 ; ( i + m - 1 ) < n ; i++){

        hasht = (((hasht - (t[i-1]*h)%MOD + MOD) * b)%MOD + t[( i + m - 1 )])%MOD;
        hash2t = (((hash2t - (t[i-1]*h2)%MOD2 + MOD2) * b)%MOD2 + t[( i + m - 1 )])%MOD2;

        if(hasht == hashp && hash2p == hash2t){

            cnt++;

            if(cnt <= 1000) poz.push_back(i);

        }

    }

    fout << cnt<< '\n';

    for( auto it : poz ){

        fout << it << ' ';
    }

    return 0;
}