Cod sursa(job #2137937)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 21 februarie 2018 10:02:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <cstring>

#define MOD1 100007
#define MOD2 100021

using namespace std;
const int b   = 73;
const int N   = 2000006;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int h1,h2;
int hb1[N];
int hb2[N];
char sir[N];
int p1,p2,m,n;

int v[1005];
int main()
{
    f>>sir;
    n = strlen(sir);
    p1 = 1;
    p2 = 1;
    for(int i = 0; i< n; i++){

        h1 = (h1*b%MOD1+sir[i])%MOD1;
        h2 = (h2*b%MOD2+sir[i])%MOD2;
        if(i!=0){
            p1 = (p1*b)%MOD1;
            p2 = (p2*b)%MOD2;
        }


    }

    //g<<h1<<" "<<h2<<"\n\n";

    f>>sir;
    m = strlen(sir);
    hb1[0] = sir[0] % MOD1;
    hb2[0] = sir[0] % MOD2;

    for(int i = 1; i< n; i++){

        hb1[i] = (hb1[i-1] * b % MOD1 + sir[i]) % MOD1;
        hb2[i] = (hb2[i-1] * b % MOD2 + sir[i]) % MOD2;

    }

    int ht1,ht2,nr = 0;

    ht1 = hb1[n-1];
    ht2 = hb2[n-1];

    if(hb1[n-1]==h1 && hb2[n-1]==h2){
        nr++;
        v[nr] = 0;
    }

    for(int i = n; i< m; i++){

        //ht1 = (hb1[i]-hb1[i-n]*p1%MOD1+MOD1)%MOD1;
        //ht2 = (hb2[i]-hb2[i-n]*p2%MOD2+MOD2)%MOD2;
        ht1 = ((ht1 - sir[i-n]*p1%MOD1+MOD1)%MOD1*b+sir[i])%MOD1;
        ht2 = ((ht2 - sir[i-n]*p2%MOD2+MOD2)%MOD2*b+sir[i])%MOD2;
        //g<<i-n<<" "<<i<<" "<<ht1<<" "<<ht2<<"\n";

        if(ht1 == h1 && ht2 == h2){
            nr++;
            if(nr<=1000)
                v[nr] = i-n+1;
        }

    }
    g<<nr<<"\n";
    for(int i =1; i<=nr&&i<=1000;i++){
        g<<v[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}