Cod sursa(job #2048648)

Utilizator Y0da1NUME JMECHER Y0da1 Data 26 octombrie 2017 13:46:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>

using namespace std;

int l, w;

char A [2000002];
char B [2000002];

bool init = 0;

int pos [1002];
int cnt = 0;
int P1 = 1, P2 = 1;
int H1 (char * w, int len)
{
    int H = 0;
    for(int i = 0; i < len; ++i)
    {
        H = (H * 57 + w[i]) % 100007;
        if(i && !init)
        {
            P1 *= 57;
            P1 %= 100007;
        }
    }
    return H;
}

int H2 (char * w, int len)
{
    int H = 0;
    for(int i = 0; i < len; ++i)
    {
        H = (H * 57 + w[i]) % 100021;
        if(i && !init)
        {
            P2 *= 57;
            P2 %= 100021;
        }
    }
    return H;
}

int naiv (char * mic, char * mare, int len)
{
    for(int i = 0; i < len; ++i)
        if(mic[i]!=mare[i])
            return 0;
    return 1;
}

int main()
{

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

    in>>A>>B;

    w = strlen(A);
    l = strlen(B);

    //cout<<w<<" "<<l<<"\n";
    int hashw1, hashw2, temp1, temp2;

    hashw1 = H1(A, w);
    hashw2 = H2(A, w);
    //cout<<hashw1<<" "<<hashw2<<"\n";
    init = true;
    int hs1, hs2;
    hs1 = H1(B, w);
    hs2 = H2(B, w);
    //cout<<"Hashuri pt starea 0: "<<hs1<<" "<<hs2<<"\n";
    for (int i = 0; i < l - w + 1; ++i)
    {
        //temp1 = H1(B + i, w);
        //temp2 = H2(B + i, w);
        if(hs1 == hashw1 && hs2 == hashw2)
        {
            //cout<<"HASH EGAL!\n";
            if(naiv(A, B + i, w))
            {
                //cout<<"AVEM MATCH LA "<<i<<"\n";
                if(cnt < 1000)
                    pos[cnt] = i;
                ++cnt;
                //cout<<i<<" ";
            }
        }
        //cout<<"Hashuri pt starea "<<i<<": "<<hs1<<" "<<hs2<<" (Expected "<<temp1<<" "<<temp2<<")\n";
        hs1 = ((hs1 - (P1 * B[i]) % 100007 + 100007) * 57 + B[i + w]) % 100007;
        hs2 = ((hs2 - (P2 * B[i]) % 100021 + 100021) * 57 + B[i + w]) % 100021;

    }
    out<<cnt<<"\n";
    for (int i = 0; i < min(cnt, 1000); ++i)
        out<<pos[i]<<" ";
    return 0;
}