Cod sursa(job #2210871)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 iunie 2018 14:51:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

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

const int CONST1 = 666013, CONST2 = 10013, base1 = 127, base2 = 131;

int Ns, Nss, subHash1, subHash2, hash1, hash2, pow1, pow2;
char subStr[2000003], str[2000003];
vector<int> a;

int main()
{
    f >> subStr >> str;

    Nss = strlen(subStr);
    Ns = strlen(str);

    pow1 = 1;
    pow2 = 1;

    for(int i = 1; i < Nss; i++) {
        pow1 = (pow1 * base1) % CONST1;
        pow2 = (pow2 * base2) % CONST2;
    }

    for(int i = 0; i < Nss; i++) {
        subHash1 = ((subHash1 * base1) % CONST1 + (subStr[i] - '0')) % CONST1;
        subHash2 = ((subHash2 * base2) % CONST2 + (subStr[i] - '0')) % CONST2;
        hash1 = ((hash1 * base1) % CONST1 + (str[i] - '0')) % CONST1;
        hash2 = ((hash2 * base2) % CONST2 + (str[i] - '0')) % CONST2;
    }



    if(subHash1 == hash1 && subHash2 == hash2)
        a.push_back(0);

    for(int i = Nss; i < Ns; i++) {
        hash1 = (((hash1 - ((str[i - Nss] - '0') * pow1)) % CONST1 + CONST1) * base1 + (str[i] - '0')) % CONST1;
        hash2 = (((hash2 - ((str[i - Nss] - '0') * pow2)) % CONST2 + CONST2) * base2 + (str[i] - '0')) % CONST2;
        if(subHash1 == hash1 && subHash2 == hash2 && a.size() < 1000)
            a.push_back(i - Nss + 1);
    }
    g << a.size() << "\n";
    for(auto &val : a)
        g << val << " ";
    g << "\n";
    return 0;
}