Cod sursa(job #2359016)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 28 februarie 2019 15:57:13
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <cstring>

#define NMAX 2000005
#define MOD1 100007
#define MOD2 100021
#define crypt 256
using namespace std;

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

char sir1[NMAX], sir2[NMAX];
vector<int> rez;
int h1 = 1, h2 = 1, lg1, lg2;

void match()
{
    int hs1 = 0;
    int hs2 = 0;

    for(int i = 0; i < lg1; ++i)
    {
        hs1 = (hs1 * crypt + sir1[i]) % MOD1;
        hs2 = (hs2 * crypt + sir1[i]) % MOD2;
    }

    int sh1 = 0;
    int sh2 = 0;
    for(int i = 0; i < lg1; ++i){
        sh1 = (sh1 * crypt + sir2[i]) % MOD1;
        sh2 = (sh2 * crypt + sir2[i]) % MOD2;
    }

    for(int i = 0; i <= lg2 - lg1; ++i)
    {
        if(sh1 == hs1 && sh2 == hs2)
            rez.push_back(i);

        if(i < lg2 - lg1)
        {
            sh1 = (crypt * (sh1 - sir2[i] * h1) + sir2[i + lg1]) % MOD1;
            sh2 = (crypt * (sh2 - sir2[i] * h2) + sir2[i + lg1]) % MOD2;
            if(sh1 < 0)
                sh1 = (sh1 + MOD1);
            if(sh2 < 0)
                sh2 = (sh2 + MOD2);
        }
    }
}

int main()
{
    fin.getline(sir1, NMAX);
    fin.getline(sir2, NMAX);

    lg1 = strlen(sir1);
    lg2 = strlen(sir2);
    for(int i = 0; i < lg1 - 1; ++i)
        h1 = (h1 * crypt) % MOD1, h2 = (h2 * crypt) % MOD2;

    match();

    fout << rez.size() << '\n';
    int stop = min((int)rez.size(), 1000);
    for(int i = 0; i < stop; ++i)
        fout << rez[i] << ' ';
    fout << '\n';
    return 0;
}