Cod sursa(job #1200366)

Utilizator toncuvasileToncu Vasile toncuvasile Data 22 iunie 2014 12:46:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int main(){
    string A, B;

    ifstream inFile("strmatch.in");
    ofstream outFile("strmatch.out");

    inFile >> A;
    inFile >> B;

    long long n = A.size(), m = B.size();

  //  outFile << A << "\n" << B << "\n" << n << " " << m;

    long long MOD1 = 100021, p = 80;
    long long hashA1 = 0, h1 = 0;

    long long MOD2 = 100007;
    long long hashA2 = 0, h2 = 0;

    for(int i=0; i<n; i++){
        hashA1 = (p*hashA1 + A[i]) % MOD1;
        h1 = (p*h1 + B[i]) % MOD1;

        hashA2 = (p*hashA2 + A[i]) % MOD2;
        h2 = (p*h2 + B[i]) % MOD2;
    }

    long long p1 = p % MOD1, p2 = p % MOD2;
    for(int i=2; i<= n; i++){ p1 = (p*p1) % MOD1; p2=(p*p2)%MOD2; }

    vector <int> V;
    if( (hashA1 == h1)&&(hashA2==h2) ){ V.push_back(0); }

    for(int i=1; i<=m-n; i++){
        h1 = (  (p*h1)%MOD1 - (B[i-1]*p1)%MOD1 + MOD1 +B[i+n-1]%MOD1  )%MOD1;
        h2 = (  (p*h2)%MOD2 - (B[i-1]*p2)%MOD2 + MOD2 +B[i+n-1]%MOD2  )%MOD2;
        if( (hashA1 == h1)&&(hashA2==h2) ) V.push_back(i);
    }

    int l = (V.size()<1000)?V.size():1000;
   // outFile << "\n";
    outFile << V.size() << "\n";
    for(int i=0; i<l; i++) outFile << V[i] << " ";

}