Cod sursa(job #1520172)

Utilizator TopiAlexTopala Alexandru TopiAlex Data 8 noiembrie 2015 13:56:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <string.h>
#define MOD1 100007
#define MOD2 100021
#define BAZA 73
#define N_MAX 2000002
using namespace std;

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

char a[N_MAX];
char b[N_MAX];
int aHash1, aHash2;
int bHash1, bHash2;
int pow1, pow2;
int sol[N_MAX];
int k;

int main()
{
    int len1, len2;
    int i;

    f >> a;
    f.get();
    f >> b;

    len1 = strlen(a);
    len2 = strlen(b);

    if (len1 > len2){
        g << 0 << '\n';
        return 0;
    }

    pow1 = pow2 = 1;
    aHash1 = aHash2 = 0;
    k = 0;

    for (i = 0; i < len1; ++i){
        aHash1 = (aHash1 * BAZA + a[i])%MOD1;
        aHash2 = (aHash2 * BAZA + a[i])%MOD2;

        if (i != 0){
            pow1 = (pow1 * BAZA)%MOD1;
            pow2 = (pow2 * BAZA)%MOD2;
        }
    }

    bHash1 = bHash2 = 0;

    for (i = 0; i < len1; ++i){
        bHash1 = (bHash1 * BAZA + b[i])%MOD1;
        bHash2 = (bHash2 * BAZA + b[i])%MOD2;
    }

    if (aHash1 == bHash1 && aHash2 == bHash2){
        sol[k++] = 0;
    }

    for (i = len1; i < len2; ++i){
        bHash1 = ((bHash1 - (b[i - len1] * pow1)%MOD1 + MOD1) * BAZA + b[i])%MOD1;
        bHash2 = ((bHash2 - (b[i - len1] * pow2)%MOD2 + MOD2) * BAZA + b[i])%MOD2;

        if (aHash1 == bHash1 && aHash2 == bHash2){
            sol[k++] = i - len1 + 1;
        }
    }

    g << k << '\n';

    for (i = 0; i < k; ++i){
        g << sol[i] << ' ';
    }

    g << '\n';

    f.close();
    g.close();

    return 0;
}