Cod sursa(job #2409696)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 19 aprilie 2019 12:45:24
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <string>
#include <vector>

#define MOD1 666013
#define MOD2 666019

using namespace std;

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

string str1, str2;

int hashSmall1, hashSmall2, hashBig1, hashBig2, pow1 = 1, pow2 = 1;

int BASE = 59, nrSol;

vector<int> sol;

int main(int argc, const char * argv[]) {
    in>>str1>>str2;
    
    if(str1.size() > str2.size()){
        out<<0;
        return 0;
    }
    
    //ABC
    
    for(auto it : str1){
        hashSmall1 = (hashSmall1 * BASE + it - 'A') % MOD1;
        hashSmall2 = (hashSmall2 * BASE + it - 'A') % MOD2;
    }
    
    for(int i = 0; i < str1.size(); ++ i){
        hashBig1 = (hashBig1 * BASE + str2[i] - 'A') % MOD1;
        hashBig2 = (hashBig2 * BASE + str2[i] - 'A') % MOD2;
        if(i != 0){
            pow1 = (pow1 * BASE) % MOD1;
            pow2 = (pow2 * BASE) % MOD2;
        }
    }
    
    if(hashBig1 == hashSmall1 && hashBig2 == hashSmall2){
        ++ nrSol;
        sol.push_back(0);
    }
    
    for(int i = str1.size(); i < str2.size(); ++ i){
        hashBig1 = hashBig1 - pow1 * (str2[i - str1.size()] - 'A') % MOD1;
        while(hashBig1 < 0)
            hashBig1 += MOD1;
        hashBig2 = hashBig2 - pow2 * (str2[i - str1.size()] - 'A') % MOD2;
        while(hashBig2 < 0)
            hashBig2 += MOD2;
        
        hashBig1 = (hashBig1 * BASE + str2[i] - 'A') % MOD1;
        hashBig2 = (hashBig2 * BASE + str2[i] - 'A') % MOD2;
        
        if(hashBig1 == hashSmall1 && hashBig2 == hashSmall2){
            ++ nrSol;
            if(nrSol < 1000)
                sol.push_back(i - str1.size() + 1);
        }
        
    }
    
    out<<nrSol<<'\n';
    for(auto it : sol)
        out<<it<<" ";
    
    
    
    return 0;
}