Cod sursa(job #1200362)

Utilizator toncuvasileToncu Vasile toncuvasile Data 22 iunie 2014 12:41:48
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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 MOD = 100021, p = 80;
    long long hashA = 0, h = 0;

    for(int i=0; i<n; i++){
        hashA = (p*hashA + A[i]) % MOD;
        h = (p*h + B[i]) % MOD;
    }

    long long p1 = p % MOD;
    for(int i=2; i<= n; i++){ p1 = (p*p1) % MOD; }

    vector <int> V;
    if(hashA == h){ V.push_back(0); }

    for(int i=1; i<=m-n; i++){
        h = (  (p*h)%MOD - (B[i-1]*p1)%MOD + MOD +B[i+n-1]%MOD  )%MOD;
        if(hashA == h) 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] << " ";

}