Cod sursa(job #2976560)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 9 februarie 2023 15:29:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;

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

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

string p , t;

vector <int> poz;

int trans( char x ){

    if( x >= 'a' ){

        return x - 'a' + 1;
    }

    if( x >= 'A'){

        return 26 + x - 'A' + 1;
    }

    return 52 + x - '0' + 1;

}

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 + trans(p[i]))%MOD;
        hasht = ((hasht*b)%MOD + trans(t[i]))%MOD;
        hash2p = ((hash2p*b)%MOD2 + trans(p[i]))%MOD2;
        hash2t = ((hash2t*b)%MOD2 + trans(t[i]))%MOD2;
    }

    if(hashp == hasht && hash2p == hash2t) poz.push_back(0);

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

        if(poz.size() == 1000) break;

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

        if(hasht == hashp && hash2p == hash2t) poz.push_back(i);

    }

    fout << poz.size()<< '\n';

    for( auto it : poz ){

        fout << it << ' ';
    }

    return 0;
}