Cod sursa(job #1780788)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 16 octombrie 2016 15:50:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <cstring>

#define prime 73
#define mod1 100007
#define mod2 100021
#define NMax 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char x[NMax],y[NMax];
int Hx1,Hy1,Hx2,Hy2,P1,P2,Sx,Sy,ans1;
vector<int> ans;

int main()
{
    f.getline(x,NMax);
    f.getline(y,NMax);
    Sx = strlen(x);
    Sy = strlen(y);

    P1 = 1;
    P2 = 1;

    for(int i = 0; i < Sx; ++i){
        Hx1 = (Hx1 * prime + x[i]) % mod1;
        Hx2 = (Hx2 * prime + x[i]) % mod2;

        if(i != 0){
            P1 = (P1 * prime) % mod1;
            P2 = (P2 * prime) % mod2;
        }
    }///calculez hashurile substringului

    for(int i = 0; i < Sx; ++i){///calculez hashurile primelor Sx litere din text
        Hy1 = (Hy1 * prime + y[i]) % mod1;
        Hy2 = (Hy2 * prime + y[i]) % mod2;
    }

    for(int i = 1; i <= Sy - Sx + 1; ++i){
        ///verific Hy
        if(Hy1 == Hx1 && Hy2 == Hx2){
            ans1++;
            if(ans1 <= 1000)
                ans.push_back(i - 1);
        }
        if(i == Sy) break;
        Hy1 = ((Hy1 - (y[i - 1] * P1) % mod1 + mod1) * prime + y[i + Sx - 1]) % mod1;///corectez functiile hasului
        Hy2 = ((Hy2 - (y[i - 1] * P2) % mod2 + mod2) * prime + y[i + Sx - 1]) % mod2;///stergand primul element si adaugant ultimul
    }
    g << ans1 << '\n';
    for(int i = 0; i < ans.size(); ++i){
        g << ans[i] << ' ';
    }
    return 0;
}