Cod sursa(job #2358994)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 28 februarie 2019 15:40:55
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <cstring>

#define NMAX 2000005
#define MOD 101
#define crypt 256
using namespace std;

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

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

int rehash(int val, int poz)
{
    val = (crypt * (val - sir2[poz] * h) + sir2[poz + lg1]) % MOD;
    return val;
}

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

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

    for(int i = 0; i <= lg2 - lg1; ++i)
    {
        if(hs1 == hs2)
        {
            bool ok = 1;
            for(int j = 0; j < lg1; ++j)
                if(sir1[j] != sir2[i + j])
                {
                    ok = 0;
                    break;
                }
            if(ok)
                rez.push_back(i);
        }

        if(i < lg2 - lg1)
        {
            hs2 = rehash(hs2, i);
            if(hs2 < 0)
                hs2 = (hs2 + MOD);
        }
    }
}

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

    lg1 = strlen(sir1);
    lg2 = strlen(sir2);
    for(int i = 0; i < lg1 - 1; ++i)
        h = (h * crypt) % MOD;

    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;
}