Cod sursa(job #2378747)

Utilizator KemyKoTeo Virghi KemyKo Data 12 martie 2019 16:31:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <string>

#define MOD1 100003
#define MOD2 100021
#define PRIM1 33
#define PRIM2 73

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string A, B;
vector <int> rez;
unsigned long long hashA1, hashA2, P1 = 1, P2 = 1, hashB1, hashB2;
int szA, szB, nr = 0;

int main()
{
    f >> A >> B;
    szA = A.size();
    szB = B.size();

    if (szA > szB){
		g << "0";
		return 0;
	}

    //hash sablon
    for(int i=0; i<szA; ++i){
        hashA1 = ((hashA1 * PRIM1) % MOD1 + A[i]) % MOD1;
        hashA2 = ((hashA2 * PRIM2) % MOD2 + A[i]) % MOD2;

        //P1 = P ^ (m-1)
        if(i!=0){
            P1 = (P1 * PRIM1) % MOD1;
			P2 = (P2 * PRIM2) % MOD2;
        }
    }

    //hash primele szA char-uri din B
    for(int i=0; i<szA; ++i){
        hashB1 = ((hashB1 * PRIM1) % MOD1 + B[i]) % MOD1;
        hashB2 = ((hashB2 * PRIM2) % MOD2 + B[i]) % MOD2;
    }

    if(hashA1 == hashB1 && hashA2 == hashB2){
        rez.push_back(0);
        ++nr;
    }

    //Restul de substringuri de lungime szA
    for(int i=szA; i<=szB; ++i){
        hashB1 = ((PRIM1 * (hashB1 - ((B[i - szA] * P1) % MOD1) )) % MOD1 + B[i]) % MOD1;
        hashB2 = ((PRIM2 * (hashB2 - ((B[i - szA] * P2) % MOD2) )) % MOD2 + B[i]) % MOD2;

        if(hashB1 == hashA1 && hashB2 == hashA2){
            rez.push_back(i - szA + 1);
            ++nr;
        }
    }

    g << nr << '\n';
    for(int i=0; i<rez.size() && i<1000; ++i)
        g << rez[i] << ' ';

    return 0;
}